鏈接：https://ac.nowcoder.com/acm/contest/330/E
來源：?？途W

精通程序設計的 Applese 叕寫了一個游戲。

在這個游戲中，有一個 n 行 m 列的方陣?，F在它要為這個方陣涂上黑白兩種顏色。規定左右相鄰兩格的顏色不能相同。請你幫它統計一下有多少種涂色的方法。由于答案很大，你需要將答案對
10
9
+
7
109+7 取模。


/*
這題容易發現規律，每一行有2種涂法（交叉式的涂），而跟有多少列沒有關系。
所以ans = 2^n%mod；
由于n特別大，所以這題重點就是高精度的計算。
高精度的 冪并且取模運算 會想到用 歐拉定理降冪+快速冪。
對于歐拉定理，有個歐拉函數：
定義：
在數論中，對于一個正整數n，歐拉函數是 小于等于n 的正整數中 與n互質的數 的數目（φ(1)=1）。

關于歐拉函數與歐拉定理和費馬小定理的關系：

歐拉定理的公式理解：
對于互質數a,m, a 的 m的歐拉值 次冪 對m取模 與 1對m取模 同余（三橫這里是同余的意思）
費馬小定理可以看成歐拉定理的一種特殊情況，即m為質數，對m取模時，m的歐拉值為m-1;
那么如何運用歐拉定理來降冪呢？

我們用歐拉定理的特殊情況費馬小定理來舉例:

2^100 % 7 = (2^(6*16)) * (2^4) % 7 =(1^16) * (2^4) % 7 = 2; 同樣上面那個例子套入降冪公式： A = 2； B =100； C = 7； 2^100 % 7 = 2^(100%φ（7）+ φ（7）) % 7; φ（7） = 6; 2^100 % 7 = 2^(100%6+ 6) % 7 = 2^(4+6) % 7 = 2^4 % 7 * 2^6 % 7 = 16%7*1 = 2;

與測試結果一致：

/
/
解題：
由于mod = 1e9 + 7，
是一個質數，所以對于本題來說可以直接用費馬小定理+快速冪
或者不管mod是不是質數（沒有考慮到mod是不是質數），用歐拉定理+快速冪；
冪指數n十分十分大，用前先結合同余定理處理
*/
ac_code(費馬+快速冪):

#include <iostream> #include <string> #define ll long long const ll mod = 1e9+7; using namespace std; ll quickPow(ll a,ll b) {ll ans = 1;a %= mod;while(b){if(b&1) ans = (ans * a) % mod;a = a * a % mod;b >>= 1;}return ans; } int main() {string s1,s2;while(cin>>s1>>s2){ll length = s1.size(),n = 0,p;p = mod - 1;for(int i = 0; i < length; i++){n =(n * 10 + (s1[i] - '0')) % p;}cout<<quickPow(2,n)<<endl;}return 0; }

ac_code(歐拉+快速冪)：

#include <iostream> #include <string> #define ll long long const ll mod = 1e9+7; using namespace std; ll quickPow(ll a,ll b) {ll ans = 1;a %= mod;while(b){if(b&1) ans = (ans * a) % mod;a = a * a % mod;b >>= 1;}return ans; } ll euler(ll n) {ll res = n;for(int i = 2; i*i <= n; i++){if(n % i == 0)res = res / i * (i-1);while(n%i==0)n /= i;}if(n > 1)res = res / n * (n-1);return res; } int main() {string s1,s2;while(cin>>s1>>s2){ll length = s1.size(),n = 0,p;//p = mod - 1;p = euler(mod);for(int i = 0; i < length; i++){n =(n * 10 + (s1[i] - '0')) % p;}cout<<quickPow(2,n)<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的Applese 涂颜色（欧拉定理降幂+快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

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