作者:mnuee | 来源:互联网 | 2023-05-18 21:07
求:3^0 + 3^1 +...+ 3^(N) mod 1000000007
Input
输入一个数N(0 <= N <= 10^9)
Output
输出:计算结果
Input示例
3
Output示例
40
很简单,这个题目是一个前N项求和的题
首先写出求和公式发现分母上有个2划开后可以变成3^n/2-1/2鉴于他是一个整型数而3^n/2-1/2=(long long)3^n/2成立,然后就想当然这样做了。但是忽略了后面的那个mod。
我们的乘方是这样定义的:
当一个数在做乘方运算时,我们规定了每一步的计算都不能溢出。所以3^1=3 % mod; 3^2=((3 %mod) * (3%mod))%mod;而问题就出在了这里
举一个简单的例子。如果我们用3^n/2去mod一个17的话。
n=2时 (int)3^2/2 mod 17=(3^2-1)/2 mod 17=4是不错。
n=4时 (int)3^3/2mod 17 = 5 而
(3^3-1)/2 mod 17= 4
WA就来自于这里
然后想了想这个除法结合着这样的乘方也是有概率会出错的。所以索性的将除以2转化为乘以2的逆元2^-1。标准的除法中,2的逆元为二分之一。但是在一个有限域中,除法的逆元就不一定是分数了
我们只要保证2*x % mod ==1 这个x就是在mod范围内2的逆元了
解出方程 x=500000004.
粘上代码:
#include
#define GP 1000000007
typedef long long ll;
ll mult(ll num,ll k)
{
ll ans=1;
while(k>0)
{
if(k&1)ans=ans*num % GP;
num=num*num % GP;
k>>=1;
}
return ans;
}
int main()
{
long long int n;
scanf("%lld",&n);
n++;
printf("%lld\n",(mult(3,n)-1)*500000004 % GP);
return 0;
}
提交 AC。