ACM暑期集训同余定理+逆元练习题

145 阅读 0 评论 96 点赞

我是靠谱客的博主英俊凉面，这篇文章主要介绍ACM暑期集训同余定理+逆元练习题，现在分享给大家，希望可以做个参考。

D - 3的幂的和

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

Input

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

Output

输出：计算结果

Sample Input

复制代码

1
3

Sample Output

复制代码

1
40

思路：Sn=(a1-an*q)/1-q，题中即要求Sn%M=( (1-3^n*3) / (1-3) ) %M=( ( 3^(n+1) -1)/2 )%M,就等于（3的n+1次方减1）乘上2的逆元这个整体%M,用扩展欧几里得模板易求出2对于1000000007的逆元为500000004，然后再用快速幂求出3的n+1次方即可

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#define M 1000000007
typedef long long ll;//注意要用long long型，否则答案错误
ll poww(ll a,ll b)
{
ll ans=1,base=a;
while(b)
{
if(b&1)
ans=ans*base%M;
base=base*base%M;
b>>=1;
}
return ans;
}
int main()
{
ll n,k;
scanf("%lld",&n);
k=(poww(3,n+1)-1)*500000004%M;
printf("%lld",k);
return 0;
}