51Nod 1013 3的幂的和 快速幂 | 乘法逆元 | 递归求和公式

时间:2023-03-08 20:17:54

51Nod 1013 3的幂的和    快速幂 | 乘法逆元 | 递归求和公式

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试一下,递归的巧妙

参考:http://blog.****.net/f_zyj/article/details/51231838