P1236 - [复赛] 指数序列求和
Description
求 1^b+2^b+...+a^b 的和除以 10000 的余数.
Input
第一行包含一个正整数 N, 表示有 N 组测试数据
接下来 N 行每行包含两个正整数 a 和 b
Output
共 N 行, 每行一个对应的答案
- Sample Input
- 1
- 2 3
- Sample Output
- 9
- Hint
数据范围:
对于 30% 数据 n≤10,a,b≤1000
对于 100% 数据 n≤100,a,b≤1000000000
Source
位运算, 二分, 快速幂
Solution
由标签和数据范围可知, 这题是个枚举模数的题.(有二分吗)
我们分析之后就会发现 a^b 和 (a+mod)^b 对答案的影响是一样的, 证明是显然的.
所以说我们对于任意 i^b 都可以写成 (i%mod)^b, 那么只需要把 mod 打表打下来就可以一次计算完了, 打表的时候用倍增快速幂即可.
-- 摘自这里
知道这个后, 这就是一个快速幂取模的水题啦!
- Code
- #include <bits/stdc++.h>
- using namespace std;
- const int mod = 10000;
- inline int read()
- {
- int f=1,x=0;
- char c=getchar();
- while(c<'0' || c>'9')
- {
- if(c=='-')f=-1;
- c=getchar();
- }
- while(c>='0' && c<='9')
- {
- x=x*10+c-'0';
- c=getchar();
- }
- return f*x;
- }
- inline int Qpow(int a,int b)
- {
- int r=1;
- while(b)
- {
- if(b&1)
- {
- r=r*a%mod;
- }
- a=a*a%mod;
- b=b>>1;
- }
- return r%mod;
- }
- int t,a,b,ans,sum;
- int main()
- {
- t=read();
- while(t--)
- {
- a=read(),b=read();
- ans=0,sum=a/mod;
- a=a%mod;
- for(register int i=1; i<=mod; i++)
- {
- if(i<=a)
- {
- ans=(ans+(sum+1)*Qpow(i,b))%mod;
- }
- else
- {
- ans=(ans+sum*Qpow(i,b))%mod;
- }
- }
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2979949.html