2 2 1000000000
6
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 #include<vector> 6 using namespace std; 7 typedef long long LL; 8 9 LL sum_mod(LL a,LL n,LL p) 10 { 11 LL ans=0; 12 n=n%p; 13 while(n) 14 { 15 if(n&1) 16 { 17 ans=ans+a; 18 if(ans>=p) ans=ans-p; 19 } 20 n=n>>1; 21 a=(a+a)%p; 22 } 23 return ans; 24 } 25 LL solve(LL a,LL n,LL p) 26 { 27 LL p1=a,p2=a,ans,i; 28 vector<LL>Q; 29 while(n) 30 { 31 ans=(n&1); 32 Q.push_back(ans); 33 n=n>>1; 34 } 35 ans=Q.size()-2; 36 for(i=ans;i>=0;i--) 37 { 38 p1=sum_mod(p1,p2+1,p); 39 p2=sum_mod(p2,p2,p); 40 if(Q[i]==1) 41 { 42 p2=sum_mod(p2,a,p); 43 p1=(p1+p2)%p; 44 } 45 } 46 return p1; 47 } 48 int main() 49 { 50 LL a,n,p; 51 while(scanf("%lld%lld%lld",&a,&n,&p)>0) 52 { 53 if(n==1){ 54 printf("%lld\n",a%p); 55 continue; 56 } 57 LL ans=solve(a,n,p); 58 printf("%lld\n",ans); 59 } 60 return 0; 61 }
nylg 640 Geometric Sum,布布扣,bubuko.com
原文:http://www.cnblogs.com/tom987690183/p/3719687.html