大部分解释来自:
http://hi.baidu.com/timer/item/ebc8c7ef908085215b2d6476
题意:
求 (1^b+ 2^b+ ... + a^b) % a
1≤a≤1000000000, 1≤b≤1000000000
思路:
a,b范围很大,直接算或者直接用快速幂取模肯定不行。
注意到题目条件:b一定是一个奇数。
观察原式,发现 [ c^b+(a-c)^b ] % a = 0 .
(证明:将 (a-c)^b 用二项式定理拆开即可)
于是这样就简单了:当a是奇数时,原式=0;当a是偶数时,原式=(a/2)^b % a .再快速幂取模即出解。
自己敲:
#include <cstdio> using namespace std; typedef long long ll; int mod; ll mypow(ll a, ll n) { ll ret = 1; while(n) { if(n%2) ret = (ret*a)%mod; a = (a*a)%mod; n >>= 1; } return ret; } int cal(int a, int b) { if(a&1) return 0; return mypow(a/2,b); } int main() { int a,b; while(scanf("%d %d",&a,&b)==2) { mod = a; printf("%d\n",cal(a,b)); } }
目前还是图样...