3的幂的模

2019-04-13 14:45发布

站内文章 / 模拟电子
12028 0 1140
class="markdown_views prism-github-gist">

3的幂的和 ##（51NOD-1013）

求：3^0 + 3^1 +…+ 3^(N) mod 1000000007
Input
输入一个数N(0 <= N <= 10^9)
Output
输出：计算结果
Sample Input
3
Sample Output
40
注释：(30+31+32+33+34)" role="presentation" style="position: relative;">(30+31+32+33+34)%1000000007" role="presentation" style="position: relative;">1000000007=40" role="presentation" style="position: relative;">=40
思路：先等比数列求和然后求模。
#include #include #include #include typedef long long ll; const ll mod=1000000007; ll pow_mod(ll a,ll b,ll c) { ll res=1; a%=c; while(b) { if(b&1) res=res*a%c; a=a*a%c; b>>=1; } return res; } //快速幂 ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll r=exgcd(b,a%b,x,y); int t=y; y=x-a/b*y; x=t; return r; //回朔得到最大公约数 } ll inv(ll a,ll mod1) //费马小定理求逆元 （任意数求逆元） { ll x,y; ll d=exgcd(a,mod1,x,y); if(d==1) return (x%mod1+mod1)%mod1; //如果x>mod则需要对mod求余，如果x<0，则要加上mod return -1; } int main() { ll n,sum; while(~scanf("%lld",&n)) { sum=0; sum=(pow_mod(3,n+1,mod)-1)*inv(2,mod)%mod; printf("%lld ",sum%mod); } return 0; } ---------- 或者是 #include #include #include using namespace std; typedef long long ll; const ll mod=1000000007; ll pow_mod(ll a,ll b,ll c) { ll res=1; a%=c; while(b) { if(b&1) res=res*a%c; a=a*a%c; b>>=1; } return res; } ll inv(ll a,ll c) //c必须是素数 { return pow_mod(a,c-2,c); } int main() { ll n,ans; while(~scanf("%lld",&n)) { ans=0; ans=(pow_mod(3,n+1,mod)-1)*inv(2,mod)%mod; printf("%lld ",ans%mod); } return 0; }

热门文章