首页 > 代码库 > nylg 640 Geometric Sum
nylg 640 Geometric Sum
Geometric Sum
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
- Compute (a + a^2 + … + a^n) mod m.(a+a2+…an)mod
- 输入
- Three integers a,n,m.
(1≤a,n,m≤10^18)
It ends with EOF. - 输出
- The only integer denotes the result.
- 样例输入
2 2 1000000000
- 样例输出
6
- 来源
- Lepus
- 矩阵里也求过a+a^2+a^3+a^4.......
-
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。