51nod 1013 3的幂的和(除法取模+快速幂）

分析：等比数列前（n+1）项和，公比为3，首项为1.所以ans=( 3^(n+1)-1 ) / 2 % 1000000007.

　　　3^(n+1)用快速幂很好解决，而除法取模只需将除法变乘法即可，也就是用被除数去乘以除数的乘法逆元.

　　　求乘法逆元用费马小定理：当模为素数，a的逆元为pow_mod(a,mod-2).

代码：

 1 //(3^(n+1)-1)/2%mod;
 2 #include <iostream>
 3 using namespace std;
 4 typedef long long ll;
 5 const int mod=1e9+7;
 6 ll ans;
 7 ll pow_mod(ll a,ll i)
 8 {
 9     ll ans=1;
10     while(i)
11     {
12         if(i&1)
13             ans=(ans*a)%mod;
14         a=(a*a)%mod;
15         i>>=1;
16     }
17     return ans;
18 }
19 int main()
20 {
21     ll n;
22     ios::sync_with_stdio(false);
23     while(cin>>n)
24     {
25         ans=pow_mod(3,n+1)-1;
26         ans=(ans*pow_mod(2,mod-2))%mod;
27         cout<<ans<<endl;
28     }
29     return 0;
30 }

View Code

1013 3的幂的和

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

取消关注

求：3^0 + 3^1 +...+ 3^(N) mod 1000000007

Input

输入一个数N(0 <= N <= 10^9)

Output

输出：计算结果

Input示例

Output示例