给定三个整数a(a>=0),n(n>=0),p(p>0)。 求解 ans=(a0+a1+…an)mod p 1≤T≤1e5
0≤a≤1e9
0≤n≤1e18
0<p≤2e9
#include<iostream> #include<cstdio> using namespace std; long long Pow(int x, long long y, int p) { if(y == 0) return 1%p; else if(y == 1) return x%p; else { long long t = Pow(x, y/2, p); if(y&1) { return t*t%p*x%p; } else { return t*t%p; } } } long long sum(int a, long long l, long long r, int p) { if(l == r) return Pow(a, l, p); else { long long len = r-l+1; long long mid = l+len/2; if(len&1) { long long x = sum(a, l, mid-1, p); long long ans = x+x*Pow(a, len/2+1, p)+Pow(a, mid, p); return ans%p; } else { long long x = sum(a, l, mid-1, p); long long ans = x+x*Pow(a, len/2, p); return ans%p; } } } int main() { int a, p; long long n; int t; scanf("%d", &t); while(t--) { scanf("%d%lld%d", &a, &n, &p); printf("%lld\n", sum(a, 0, n, p)); } return 0; }