洛谷 P4942 小凯的数字 逆元

题目背景

NOIP2018 原创模拟题T1

NOIP DAY1 T1 or DAY 2 T1 难度

是否发现与NOIP2017 DAY1 T1 有异曲同工之妙

#10 输入格式存在问题，对于 python 选手请特判空行。待修复。

题目描述

小凯有一天突发奇想，写下了一串数字：l(l+1)(l+2)…(r-1)rl(l+1)(l+2)…(r−1)r

例如：l=2,r=5l=2,r=5时，数字为：23452345

l=8,r=12l=8,r=12时数字为：8910111289101112

小凯很喜欢数字9，所以他想问你他写下的数字除以9的余数是多少

例如：l=2,r=5l=2,r=5时，2345 mod 9 = 5

输入格式

第一行为数字Q,表示小凯有Q个问题

第2-Q+1行，每行两个数字 l,r 表示数字范围

输出格式

对于每行的问题输出一行，一个数字，表示小凯问题的回答

输入 #1

2
2 5
8 12

输出 #1

5
5

输入 #2

3
1 999
123 456
13579 24680

输出 #2

0
6
0

说明/提示

样例1解释：2345 mod 9 = 5 89101112 mod 9 = 5

30% 数据满足：Q<=10;l,r<=100

50% 数据满足：Q<=100;l,r<=10000

70% 数据满足：Q<=1000;l,r<=10^6

100%数据满足：Q<=10000;0

分析

因为10^n对9取模都等于1，所以一个数字如123456789对9取模等于（1+2+3+4+5+6+7+8+9）对9取模。
所以可以这样求得答案（ l + r ） * （ r -l + 1 ）% 9
但是因为题目的数据有点大，可以进行变形。
l=l%9，r=（r%9）+9，除以2等于乘以2对9的逆元5.

#include
#define ll unsigned long long
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
inline ll rd()
{register ll s=0,w=1;register char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar(); }while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*w;
}
int main()
{int q;q=rd();while(q--){ll l,r;l=rd(),r=rd();l=l%9,r=r%9;if(r<l) r=r+9;int ans=(r+l)*(r-l+1)*5%9;printf("%d\n",ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！