Applese涂颜色

题目链接： https://ac.nowcoder.com/acm/contest/330/E

费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有$a^{p-1}≡1(mod p)$。

在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则: $a^{φ(n)}≡1(mod n)$
φ(n)为欧拉函数，定义为不超过n的整数中与n互素的个数。
欧拉降幂公式： $a^b≡a^{bmodφ(n)+φ(n)}mod n$

题意：求出$2^n$。
思路：快速幂求$2^n$，问题是n太大了。肯定用数组存，然后利用
费马小定理：$2^nmod m=2^{n mod (m-1）}modm$ （这个怎么推我还不知道）

我写的AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
//快速幂
ll mod_pow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

int main(){
    string n,m;
    ll a;
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        a=0;
        for(ll i=0;i<n.size();i++){
            a=(a*10+n[i]-'0')%(mod-1);   
        }
        printf("%lld\n",mod_pow(2,a));
    }
    return 0;
}