欧拉定理及推论

　

欧拉定理

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

来源：牛客网

有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大，你需要将答案对1e9+7  取模。

输入描述:

仅一行两个正整数 n, m，表示方阵的大小。

输出描述:

输出一个正整数，表示方案数对 1e9+7取模。

输入

2 2

输出

4

备注:

1≤n,m≤10^100000

题解

这道题答案是2的n次幂，因为n范围很大，所以不能直接快速幂来算。

欧拉定理的推论：

如果正整数a,n互质，则对于任意正整数b，满足   ，其中为欧拉函数

这道题用这个公式就可以算出来了。

如果a,n不一定互质且b>时，有

费马小定理

若p为质数，则对于任意的a，有

欧拉定理

若正整数a,n互质，则

代码

#include<algorithm>
#include <iOStream>
#include<cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int mod=1e9+7;
const int euler=1e9+6;
char a[maxn];
ll ksm(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1) ans=ans*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans;
}
int main(){
    scanf("%s",a);
    int len=strlen(a);
    ll x=0;
     for(int i=0;i<len;i++){
          x=(x*10+a[i]-'0')%euler;
     }
    cout<<ksm(2,x)<<endl;
    return 0;
}

相关阅读

欧拉函数

原文链接：https://zh.m.wikipedia.org/zh/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0 欧拉函数 本文介绍的是小于或等于n的正整数中与n

三个重要的同余式——威尔逊定理，费马小定理，欧拉定理（扩

鸣谢synapse7大大 威尔逊定理 (p−1)!≡p−1≡−1   (mod p) (p

区间套定理

闭区间列{[an,bn]}\{[a_n,b_n]\}{[an​,bn​]}有性质： [an+1,bn+1]⊂[an,bn][a_{n+1},b_{n+1}]\subset[a_n,b_n][an+1​,bn+1

欧拉角 图解释

定义 先引wiki上的定义 欧拉角：由三个角度组成，在特定坐标系下用于描述刚体的orientation.简单来说，就是绕一个三维坐标系统下的三个

香农三大定理

香农三大定理是信息论的基础理论。香农三大定理是存在性定理，虽然并没有提供具体的编码实现方法，但为通信信息的研究指明了方向。香