本文主要是介绍等比数列求和快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
CF-678D
看求的和(a^n-1)/(a-1)按奇偶递推
#include<iostream>
using namespace std;
const long long m=1e9+7;
long long mul(long long a,long long b)
{long long t=a%m,res=0;while(b){if(b&1){res+=t;if(res>m) res-=m;}t<<=1;if(t>m) t-=m;b>>=1;}return res;
}
long long pow_mod(long long a,long long b)
{long long t=a%m,res=1;while(b){if(b&1) res=mul(res,t);t=mul(t,t);b>>=1;}return res;
}
long long fun(long long a,long long b,long long n)
{if(n==1) return b;if(n&1) return fun(a,b,n-1)+mul(b,pow_mod(a,n-1));else return fun(mul(a,a),mul(a+1,b),n>>1);
}
int main()
{long long a,b,x,n,g=0;cin>>a>>b>>n>>x;g+=mul(x,pow_mod(a,n));if(a==1) g+=mul(b,n);else g+=(fun(a,b,n));g%=m;cout<<g<<endl;
}
这篇关于等比数列求和快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
