拓展欧拉定理（欧拉降幂，Sum，上帝与集合的正确用法，Brute-force Algorithm）

一、介绍

1.内容

$$a^b\%m=?\begin{array}{ll}{a}^{b\%\phi (m)}\%m& gcd(a,m)=1\\ a^b\%m& gcd(a,m)!=1且\phi (m)\ge b\\ a^{b\%\phi (m)+\phi (m)}\%m& gcd(a,m)!=1且\phi (m)<b\end{array}$$

2.作用

主要用于解决$a^b\%m$时，b过大的情况，

1. 当 gcd(a,m)=1时
   根据欧拉定理，存在$a^{\phi (m)}\equiv 1(modm)$,b可以表示为$k?\phi (m)+c(k\ge 0)$,所以$a^b\%m$可以直接表示为$((a^{k\phi (m)}\%m)(a^{b\%\phi (m)}\%m))\%m$
   也就是$a^{b\%\phi (m)}\%m$

2. gcd(a,m)!=1且$\phi (m)\ge b$
   既然$\phi (m)\ge b$，说明b的大小其实在可接受的范围内，所以可以直接使用快速幂。

3. gcd(a,m)!=1且$\phi (m)<b$
   这种情况才是欧拉降幂最常使用的情况，即无法直接使用欧拉定理，b的大小也极为恐怖。
   想要对b进行缩小，就可以直接套用公式$a^b\%m=a^{b\%\phi (m)+\phi (m)}\%m$
   别人的证明

二、例题

1.Sum

Sum
大意：给定一个N，N可以表示为若干个正整数之和，求总共的组合数。

分析：
一个N可以理解为N个1相加的结果，此时一种组合其实对应的是这N个1的分组情况，那么就可以理解为对连接这N个1的加号的处理，选择不同的加号并将其取消，就把整体划分为了不同的组。
而每个加法都有两种操作，要么保留，要么取消，所以结果其实就是$2^{N?1}$

求$2^{N?1}$时，已知1e9+7是一个质数，所以2与其为互质关系，就直接使用欧拉函数进行欧拉降幂，使用公式：
$a^b\%m=a^{b\%\phi (m)}\%m$

注意其中要对高精度取模。

代码：

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int m=1e9+7;
ll quick_multiply(ll a,ll b,ll mod){
    ll ans=0;a%=mod;b%=mod;while(b){
    if(b&1) ans=(ans+a)%mod;b>>=1;a=(a+a)%mod;}return ans;
}
ll Pow(ll a,ll b,ll mod){
    ll ans=1;a%=mod;while(b){
    if(b&1) ans=quick_multiply(ans,a,mod);b>>=1;a=quick_multiply(a,a,mod);}return ans%mod;
}
int main(){
    ll phi=m-1;string n;while(cin>>n){
    //先求n%phi ll ans=0;for(int i=0;i<n.length();i++){
    ans=(ans*10+n[i]-'0')%phi;}ans=(-1+ans+phi)%phi;//再求（n-1）%phi，注意符号要为正 cout<<Pow(2,ans,m)<<endl;}
}

2.上帝与集合的正确用法

上帝与集合的正确用法
大意：

分析：
设一开始的2的指数为k，，那么一开始是求$2^k\%p$的结果，题目提示可以默认为无限次，所以必定存在关系：k远大于φ( p)，那么就套用第三类公式，得：
$2^k\%p=2^{k\%\phi (p)+\phi (p)}\%p$，问题发生变化，此时需要求另一个式子$k\%\phi (p)$,在这个式子中，k保持了一致，仍然是无限次，而φ( p)相较于p进行了缩减，所以我们可以用递归来把问题不断分解下去；
而最终，φ(p )一定会缩减为最小的情况，即$\phi (p)=1$，当$\phi (p)=1$时，再套用公式，结果就变得唯一了，p要么为1要么为2，这个结果再对p取模一定为0，所以0就是我们的递归出口。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll euler(ll n){
      ll ans=n;  for(int i=2;i*i<=n;i++){
      if(n%i==0){
      ans-=ans/i;  while(n%i==0){
      n/=i;  }  }  }  if(n>1) ans-=ans/n;  return ans;  
}
ll qk(ll a,ll b, ll m){
    ll ans=1;while(b){
    if(b%2==1) ans=(ans*a)%m;b/=2;a=(a*a)%m;}return ans%m;
}
ll f(ll x){
    if(euler(x)==1){
    return 0;}return qk(2,f(euler(x))+euler(x),x);
}
int main(){
    int t;cin>>t;while(t--){
    ll n;cin>>n;cout<<f(n)<<endl;}return 0;
}

3.Brute-force Algorithm

Brute-force Algorithm
大意：
给定了a,b,n,p,p是要取的模，n指要返回第n个数
第一项为$a$;
第二项为$b$;
第三项为$ab$;
第四项为$a{b}^2$;
第五项为$a^2{b}^3$;
……
由观察可知，在$n\ge 3$时，每一项都是前两项之积，每一项中a与b的指数所对应的都是斐波那契数列中的一位。

分析：
此时由n本来可以直接求出a与b的指数，但由于n的范围过大，所以不适合递推求解，需要使用之前的矩阵快速幂，加快求解速度。
过程中注意对矩阵元素取模，矩阵元素代表的是指数，所以要根据欧拉降幂进行取模

for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++){
    tmp[i][j]=tmp[i][j]+a[i][k]*b[k][j];if(tmp[i][j]>phi)//当系数大于phi(p)是才能第三类降幂tmp[i][j]=tmp[i][j]%phi+phi;}

知道指数后，再对结果进行一次快速幂取模运算，把a和b对应的结果相乘，再取模就是最终的结果。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,a,b,p,phi,n,c,d,m[3][3],ans[3][3];
//c，d分别保存a，b的系数，m存斐波拉契的矩阵，ans存最后结果的矩阵，phi保存p的欧拉函数值ll euler(ll n){
    int m=sqrt(n+0.5);ll ret = n;for(int i=2;i<=m;i++){
    if(n%i==0){
    ret = ret / i * (i - 1);while(n%i==0) n/=i;}}if(n>1) ret = ret / n * (n-1);return ret;
}void multi(ll a[][3],ll b[][3]){
    //矩阵快速幂计算斐波拉契数列的第n项ll tmp[3][3];memset(tmp,0,sizeof tmp);for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++){
    tmp[i][j]=tmp[i][j]+a[i][k]*b[k][j];if(tmp[i][j]>phi)//当系数大于phi(p)是才能第三类降幂tmp[i][j]=tmp[i][j]%phi+phi;}for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)a[i][j]=tmp[i][j];
}ll quick(ll x,ll y){
    ll ans=1;while(y){
    if(y&1)ans=ans*x%p;x=x*x%p;y>>=1;}return ans;
}void quick_pow(ll x){
    //矩阵快速幂 while(x){
    if(x&1)multi(ans,m);multi(m,m);x>>=1;}
}void init(){
    //矩阵初始化memset(ans,0,sizeof ans);ans[1][1]=ans[2][2]=1;m[1][1]=m[1][2]=m[2][1]=1,m[2][2]=0;
}int main(){
    cin>>t;for(int i=1;i<=t;i++){
    cin>>a>>b>>p>>n; phi=euler(p);init();if(n==1)c=1,d=0;else if(n==2)c=0,d=2;else{
    quick_pow(n-2);c=ans[1][2],d=ans[1][1];}ll q=quick(a,c)*quick(b,d)%p;printf("Case #%d: %lld\n",i,q);}return 0;
}