Applese 涂颜色（欧拉定理降幂+快速幂）

链接：https://ac.nowcoder.com/acm/contest/330/E
来源：牛客网

精通程序设计的 Applese 叕写了一个游戏。

在这个游戏中，有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大，你需要将答案对
10
9
+
7
109+7 取模。
Applese 涂颜色（欧拉定理降幂+快速幂）

/*
这题容易发现规律，每一行有2种涂法（交叉式的涂），而跟有多少列没有关系。
所以ans = 2^n%mod；
由于n特别大，所以这题重点就是高精度的计算。
高精度的幂并且取模运算会想到用 欧拉定理降幂+快速幂。
对于欧拉定理，有个欧拉函数：
定义：
在数论中，对于一个正整数n，欧拉函数是小于等于n 的正整数中与n互质的数的数目（φ(1)=1）。
Applese 涂颜色（欧拉定理降幂+快速幂）
关于欧拉函数与欧拉定理和费马小定理的关系：

欧拉定理的公式理解：
对于互质数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;

与测试结果一致：

Applese 涂颜色（欧拉定理降幂+快速幂）
/
/
解题：
由于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 涂颜色（欧拉定理降幂+快速幂）

相关推荐