?

?

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=10010; LL quick_pow(LL a,LL b) {LL ans=1;while(b>0){if(b&1){ans=ans*a%MOD;}b>>=1;a=a*a%MOD;}return ans; } int main() {int n;LL sum;while(~scanf("%d",&n)){sum= (quick_pow(3, n+1) - 1) * 500000004 % MOD;///求2的逆元即可.因為2 * ? = 1 (mod 1000000007) ? = 500000004///而不是簡單的(quick_pow(3, n+1) - 1) /2 % mod;遇到mod /將/轉變為*除數的逆元printf("%lld\n",sum);}return 0; }

?擴展歐幾里得求乘法逆元

const int mod=1000000007; long long inv(long long a) {if(a==1)return 1;return inv(mod%a)*(mod-mod/a)%mod; } int main() {cout<<inv(2)<<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=10010; ll c; ll power(ll a, ll b) {ll ans = 1;while (b){if (b & 1){ans = (ans * a) % _MOD;}b >>= 1;a = (a * a) % _MOD;}return ans; }ll sum(ll a, ll k) {if (k == 1){return a;}c = sum(a, k >> 1); ///前k／2個次冪的和///ans等于前k/2個次冪的和加上接著的k/2個次冪的和（前k/2個次冪的和乘以第k/2個數的次冪）ll ans = (c + c * power(a, (k >> 1))) % _MOD;///加上最后一個奇數次方值if (k & 1){ans = (ans + power(a, k)) % _MOD;}return ans; }int main() {ll n;scanf("%lld", &n);printf("%lld\n", ((sum(3, n) % _MOD)) + 1);return 0; }

?帶入 4、5試一下，遞歸的巧妙

?

參考：http://blog.csdn.net/f_zyj/article/details/51231838

?

轉載于:https://www.cnblogs.com/kimsimple/p/7634365.html

總結

以上是生活随笔為你收集整理的51Nod 1013 3的幂的和 快速幂 | 乘法逆元 | 递归求和公式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。