概述
D - 3的幂的和
求：3^0 + 3^1 +...+ 3^(N) mod 1000000007
Input
输入一个数N(0 <= N <= 10^9)
Output
输出：计算结果
Sample Input
3Sample Output
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次方即可
代码：
#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;
}
最后
以上就是英俊凉面为你收集整理的ACM暑期集训 同余定理+逆元 练习题的全部内容，希望文章能够帮你解决ACM暑期集训 同余定理+逆元 练习题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复