1.乘法逆元
直接使用等比数列求和公式,注意使用乘法逆元
---严谨,失细节毁所有
#include "bits/stdc++.h"
using namespace std;
#define rep(i, s, n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define LL long long
const int N=;
LL quick_pow(LL a,LL b)
{
LL ans=;
while(b>){
if(b&){
ans=ans*a%MOD;
}
b>>=;
a=a*a%MOD;
}
return ans;
}
int main()
{
int n;
LL sum;
while(~scanf("%d",&n)){
sum= (quick_pow(, n+) - ) * % MOD;
///求2的逆元即可.因为2 * ? = 1 (mod 1000000007) ? = 500000004
///而不是简单的(quick_pow(3, n+1) - 1) /2 % mod;遇到mod /将/转变为*除数的逆元
printf("%lld\n",sum);
}
return ;
}
扩展欧几里得求乘法逆元
const int mod=;
long long inv(long long a)
{
if(a==)
return ;
return inv(mod%a)*(mod-mod/a)%mod;
}
int main()
{
cout<<inv()<<endl;
}
2.思维,构造递归求和公式
#include "bits/stdc++.h"
using namespace std;
#define rep(i, s, n) for(int i=s;i<n;i++)
#define _MOD 1000000007
#define ll long long
const int N=;
ll c;
ll power(ll a, ll b)
{
ll ans = ;
while (b)
{
if (b & )
{
ans = (ans * a) % _MOD;
}
b >>= ;
a = (a * a) % _MOD;
}
return ans;
} ll sum(ll a, ll k)
{
if (k == )
{
return a;
}
c = sum(a, k >> ); ///前k/2个次幂的和
///ans等于前k/2个次幂的和加上接着的k/2个次幂的和(前k/2个次幂的和乘以第k/2个数的次幂)
ll ans = (c + c * power(a, (k >> ))) % _MOD;
///加上最后一个奇数次方值
if (k & )
{
ans = (ans + power(a, k)) % _MOD;
}
return ans;
} int main()
{
ll n;
scanf("%lld", &n);
printf("%lld\n", ((sum(, n) % _MOD)) + );
return ;
}
带入 4、5试一下,递归的巧妙