费马小定理 & 欧拉定理
**## Part 1：知识点
费马小定理
若 \(p\) 为质数，\(a\perp p\)，则 \(a^{p - 1} \equiv 1 \pmod{p}\)
欧拉定理
若 \(a\perp n\)，则 \(a^{\varphi(n)} \equiv 1 \pmod{n}\)
（不会欧拉函数的点这里）
证明：
设 \(\{\bar{r_1}, \bar{r_2}, \cdots, \bar{r_{\varphi(n)}}\) 为 \(n\) 的一个简化剩余系，则 \(\{\bar{ar_1}, \bar{ar_2}, \cdots, \bar{ar_{\varphi(n)}\}}\) 也为 \(n\) 的一个简化剩余系。
所以 \(r_1r_2 \cdots r_{\varphi(n)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(n)} \equiv a^{\varphi(n)}r_1r_2 \cdots r_{\varphi(n)} \pmod{m}\)
约去 \(r_1r_2 \cdots r_{\varphi(n)}\)，可得 \(a^{\varphi(n)} \equiv 1 \pmod{n}\)。
当 \(p\) 是质数时，\(\varphi(p)=p-1\)，代入欧拉定理中可得费马小定理
扩展欧拉定理
\(a^b \equiv \begin{cases}a^{b \bmod \varphi(n)}&\gcd(a,n) = 1 \\ a^b &\gcd(a,n)\ne 1, b < \varphi(n) \\ a^{b \bmod \varphi(n) + \varphi(n)} &\gcd(a,n)\ne 1, b \ge \varphi(n) \end{cases} \pmod n\)
一道试水模板题【模板】扩展欧拉定理
Part 2：一些习题
1、P4861 按钮
求最小的 \(x\) 使得 \(a^x\equiv 1\pmod m\)
由 \(\mathrm{Bézout}\) 定理知当 \(\gcd(a,m)\neq1\) 时无解
由欧拉定理知 \(a^{\varphi(m)}\equiv 1\pmod m\)
但 \(\varphi(m)\) 不一定是最小的 \(x\)。不过我们可以大概猜出 \(x\mid \varphi(m)\)，下面就来证明一下：
证明： 设 \(x\) 为最小的解，且 \(x\nmid \varphi(m)\)
那么显然 \(a^{\varphi(m)-kx}\equiv 1\pmod m\quad(kx<\varphi(m))\)
则有 \(a^{\varphi(m)\bmod x}\equiv 1\pmod m\)
此时 \(\varphi(m)\bmod x<x\)，这与 \(x\) 是最小的解矛盾
所以 \(x\mid \varphi(m)\)
那我们可以 \(O(\sqrt{\varphi(m)})\) 暴力枚举每个约数，快速幂验证一下即可
#include<bits/stdc++.h>
using namespace std;
int a,m,p,ans;
int gcd(int x,int y)
{
if(y==0)
return x;
return gcd(y,x%y);
}
int get_phi(int x)
{
int res=x;
for(int i=2; i*i<=x; i++)
{
if(x%i==0)
{
res=res/i*(i-1);
while(x%i==0)
x/=i;
}
}
if(x>1)
res=res/x*(x-1);
return res;
}
int ksm(int x,int y)
{
if(y==0)
return 1;
if(y==1)
return x%m;
int tmp=ksm(x,y/2);
if(y%2==0)
return 1LL*tmp*tmp%m;
return 1LL*tmp*tmp%m*x%m;
}
int main()
{
scanf("%d%d",&m,&a);
p=get_phi(m);
ans=p;
if(gcd(a,m)!=1)
{
printf("Let's go Blue Jays!");
return 0;
}
for(int i=1; i*i<=p; i++)
{
if(p%i!=0)
continue;
if(ksm(a,i)==1)
ans=min(ans,i);
else if(ksm(a,p/i)==1)
ans=min(ans,p/i);
}
printf("%d",ans);
return 0;
}
2、P4139 上帝与集合的正确用法
即求 \(2^{2^{2^{2\cdots}}}\bmod p\)
因为幂塔是无穷的，显然大于 \(\varphi(p)\)，根据扩展欧拉定理有 \(2^{2^{2^{2\cdots}}}\equiv 2^{{2^{2^{2\cdots}}}\bmod \varphi(p)+\varphi(p)}\pmod p\)
显然是个递归的式子。又因为欧拉函数不断地迭代最终必定取到 \(1\)，所以递归暴力计算即可
#include<bits/stdc++.h>
using namespace std;
const int N=10000010;
int T,p,phi[N],v[N],prime[N],tot;
void primes()
{
phi[1]=1;
for(int i=2; i<=1e7; i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1; j<=tot; j++)
{
if(prime[j]>v[i] || prime[j]>1e7/i)
break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
phi[i*prime[j]]=phi[i]*prime[j];
else
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int pow(int a,int b,int mod)
{
if(b==0)
return 1;
if(b==1)
return a%mod;
int tmp=pow(a,b/2,mod);
if(b%2==0)
return 1LL*tmp*tmp%mod;
return 1LL*tmp*tmp%mod*a%mod;
}
int calc(int n)
{
if(n==1)
return 0;
return pow(2,calc(phi[n])+phi[n],n);
}
int main()
{
primes();
scanf("%d",&T);
while(T--)
{
scanf("%d",&p);
printf("%d\n",calc(p));
}
return 0;
}
3、P3934 [Ynoi2016] 炸脖龙 I
我愿称之为相逢是问候的前置题
操作 \(1\) 构造差分数组，树状数组修改即可。下面重点考虑操作 \(2\)
根据第2题的结论，幂塔不断迭代最后为定值，而迭代次数为使得 \(\varphi(\varphi(\cdots\varphi(p)\cdots))=1\) 的迭代次数，是 \(\log p\) 级别
因此我们考虑像上一题一样暴力递归即可。但注意，此时指数不一定大于等于 \(\varphi(p)\)，所以要加一个全局变量 \(flag\) 记录一下。直接在快速幂中记录即可。具体实现时可以先不取模，判断完再取模
代码实现细节多，写在代码注释中
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=500010,M=20000010;
int n,m,phi[M],prime[M],tot,v[M];
bool flag;
LL c[N];
void prework() //预处理1~2e7所有的phi值
{
phi[1]=1;
for(int i=2; i<=2e7; i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1; j<=tot; j++)
{
if(prime[j]>v[i] || prime[j]>2e7/i)
break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
phi[i*prime[j]]=prime[j]*phi[i];
else
phi[i*prime[j]]=(prime[j]-1)*phi[i];
}
}
}
void add(int x,int y)
{
for(x; x<=n+1; x+=(x&-x))
c[x]+=(LL)y;
}
LL ask(int x)
{
LL res=0;
for(x; x; x-=(x&-x))
res+=c[x];
return res;
}
LL ksm(LL x,LL y,LL mod)
{
flag=0;
LL res=1;
if(x>=mod) //大坑点!!!!
x%=mod,flag=1;
while(y)
{
if(y&1)
res*=x;
x*=x;
if(res>=mod) //判断两次
res%=mod,flag=1;
if(x>=mod)
x%=mod,flag=1;
y>>=1;
}
return res;
}
LL dfs(int now,LL p,int k)
{
flag=0;
LL cur=ask(now);
if(p==1 || now==k)
{
if(cur>=p) //注意要判断
flag=1,cur%=p;
return cur;
}
LL tur=dfs(now+1,phi[p],k);
return ksm(cur,flag? tur+(LL)phi[p]:tur,p); //注意指数选择的情况
}
int main()
{
prework();
scanf("%d%d",&n,&m);
for(int i=1,last=0; i<=n; i++)
{
int x;
scanf("%d",&x);
add(i,x-last); //差分数组
last=x;
}
for(int i=1; i<=m; i++)
{
int op,l,r,x,p;
scanf("%d%d%d",&op,&l,&r);
if(op==1)
{
scanf("%d",&x);
add(l,x); add(r+1,-x);
}
else
{
scanf("%d",&p);
printf("%lld\n",dfs(l,(LL)p,r));
}
}
return 0;
}
4、P3747 [六省联考 2017] 相逢是问候
一道线段树+扩展欧拉定理的毒瘤题
建议先做P4145 上帝造题的七分钟 2 / 花神游历各国
操作 \(1\) 一眼线段树。重点考虑操作 \(0\)
根据第2题的结论，\(c^{c^{c^{a_i}}}\) 不断迭代最后为定值，而迭代次数 \(tphi\) 为使得 \(\varphi(\varphi(\cdots\varphi(p)\cdots))=1\) 的迭代次数，是 \(\log p\) 级别
因此，类似上帝造题的7分钟2，我们对线段树的每个叶子节点记录一个迭代次数 \(t\)，区间的 \(t\) 取左右儿子的最小值。当区间的 \(t\) 大于等于 \(tphi\) 时不递归。对于叶子节点的修改，类似上一题一样 \(\mathrm{dfs}\) 迭代 \(t\) 次即可。欧拉函数可预处理出来，只预处理有用的即可。注意因为最顶上的数是 \(a_i\) 不是 \(c\)，所以欧拉函数最后要放两个 \(1\)
注意到这题的指数不一定大于 \(\varphi(p)\)，像上一题一样判断即可，实现略有出入
时间复杂度为 \(O(n\log^3p)\)，每个叶子节点修改 \(n\log p\)，每个位置递归欧拉函数 \(\log p\) 层，计算时还得快速幂 \(\log p\)。这样显然无法通过。注意到只有 \(\log p\) 种模数，所以可以将快速幂换成光速幂，即 \(c^{a}=c^{10000\times k}\times c^t\)。这样可以 \(O(\sqrt{p})\) 预处理，\(O(1)\) 回答，省去一个 \(\log\)
#include<bits/stdc++.h>
#define LL long long
#define lc(p) p*2
#define rc(p) p*2+1
using namespace std;
const int N=50010,M=50,MAXN=10010;
struct SegmentTree
{
LL sum,t;
#define sum(x) tree[x].sum
#define t(x) tree[x].t
}tree[4*N];
int n,m,phi[M],tphi;
LL P,c,a[4*N],pow1[MAXN][M],pow2[MAXN][M];
bool b1[MAXN][M],b2[MAXN][M],flag;
int get_phi(int x)
{
int res=x;
for(int i=2; i*i<=x; i++)
{
if(x%i==0)
{
res=res/i*(i-1);
while(x%i==0)
x/=i;
}
}
if(x>1)
res=res/x*(x-1);
return res;
}
void prework()
{
LL tmp=P;
phi[0]=P; //预处理有用的phi
while(tmp!=1)
tmp=get_phi(tmp),phi[++tphi]=tmp;
phi[++tphi]=1;
for(int i=0; i<=tphi; i++) //光速幂
{
pow1[0][i]=1;
for(int j=1; j<=10000; j++)
{
pow1[j][i]=pow1[j-1][i]*c;
if(pow1[j][i]>=phi[i])
pow1[j][i]%=phi[i],b1[j][i]=1;
b1[j][i]|=b1[j-1][i]; //判断是扩展欧拉定理的哪种情况
}
}
for(int i=0; i<=tphi; i++)
{
pow2[0][i]=1;
b2[1][i]=b1[10000][i];
for(int j=1; j<=10000; j++)
{
pow2[j][i]=pow2[j-1][i]*pow1[10000][i];
if(pow2[j][i]>=phi[i])
pow2[j][i]%=phi[i],b2[j][i]=1;
b2[j][i]|=b2[j-1][i];
}
}
}
LL calc(LL x,int k) //O(1)回答
{
flag=0;
LL x1=x%10000,x2=x/10000;
LL res=pow1[x1][k]*pow2[x2][k];
if(res>=phi[k])
res%=phi[k],flag=1;
flag|=b1[x1][k]|b2[x2][k];
return res;
}
LL dfs(LL cur,int dep,int k) //递归log_p层
{
flag=0;
if(dep==k)
{
if(cur>=phi[dep])
flag=1,cur%=phi[dep];
return cur;
}
LL tur=dfs(cur,dep+1,k);
return calc(flag? tur+phi[dep+1]:tur,dep);
}
void pushup(int p)
{
t(p)=min(t(lc(p)),t(rc(p)));
sum(p)=(sum(lc(p))+sum(rc(p)))%P;
}
void build(int p,int l,int r)
{
if(l==r)
{
scanf("%d",&a[p]);
sum(p)=a[p];
return;
}
int mid=(l+r)>>1;
build(lc(p),l,mid);
build(rc(p),mid+1,r);
pushup(p);
}
void change(int p,int l,int r,int ql,int qr)
{
if(t(p)>=tphi) //没有必要继续修改
return;
if(l==r)
{
t(p)++;
sum(p)=dfs(a[p],0,t(p));
return;
}
int mid=(l+r)>>1;
if(ql<=mid && t(lc(p))<tphi)
change(lc(p),l,mid,ql,qr);
if(qr>mid && t(rc(p))<tphi)
change(rc(p),mid+1,r,ql,qr);
pushup(p);
}
LL ask(int p,int l,int r,int ql,int qr)
{
if(ql<=l && qr>=r)
return sum(p);
int mid=(l+r)>>1;
LL val=0;
if(ql<=mid)
val+=ask(lc(p),l,mid,ql,qr);
if(qr>mid)
val+=ask(rc(p),mid+1,r,ql,qr);
return val%P;
}
int main()
{
scanf("%d%d%lld%lld",&n,&m,&P,&c);
prework();
build(1,1,n);
for(int i=1; i<=m; i++)
{
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==0)
change(1,1,n,l,r);
else
printf("%lld\n",ask(1,1,n,l,r));
}
return 0;
}
**