欧拉定理：
若正整数 \(a,n\) 互质，则 \(a^{\varphi(p)}\equiv1(\bmod p)\)
推论（扩展欧拉定理）：
\[a^b\equiv\begin{cases} a^{b\ \bmod\ \varphi(p)}\ \ \ \ \ \ \ \ \ \gcd(a,p)=1\\ a^b\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \gcd(a,p)!=1,b<\varphi(p)\ \ \ \ \ (\bmod p)\\ a^{b\ \bmod\ \varphi(p)+\varphi(p)}\ \gcd(a,p)!=1,b\geq\varphi(p) \end{cases} \]证明： \(a^b\equiv a^{b\ \bmod\ \varphi(p)}\ \ \gcd(a,p)=1\)
\[设 b=q\times \varphi(p)+r\\ a^b\equiv a^{q\times\varphi(p)+r}\equiv (a^{\varphi(p)})^q\times a^r\equiv 1^q\times a^r\equiv a^r\equiv a^{b\ \bmod\ \varphi(p)} \]
若正整数 \(a,n\) 互质，则满足 \(a^x\equiv 1(\bmod n)\) 的最小正整数 \(x_0\) 是 \(\varphi(n)\) 的约数。
假设满足 \(a^x\equiv 1(\bmod n)\) 的最小正整数 \(x_0\) 不是 \(\varphi(n)\) 的约数。
设 \(\varphi(n)=qx_0+r(0<r<x_0)\)
\(\therefore a^{x_0}\equiv 1(\bmod n)\)
\(\therefore a^{qx_0}\equiv 1(\bmod n)\)
\(\because a^{\varphi(n)}\equiv 1(\bmod n)\)
\(\therefore a^r\equiv 1(\bmod n)\)
而 \(r<x_0\) ，这与 \(x_0\) 最小矛盾，所以假设不成立。
例： 求 \(a^b\bmod m\) ？
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e7+10;
int a, m;
char b[maxn];
int phi(int x) {
int res = x;
int cnt = sqrt(x);
for(int i=2; i<=cnt; ++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;
}
LL quick_pow(LL x, LL y) {
LL res = 1;
while(y) {
if(y&1)
res = (res*x)% m;
x = (x*x) % m;
y >>= 1;
}
return res % m;
}
int main () {
scanf("%d%d%s", &a, &m, b);
int Phi = phi(m); // m 的欧拉函数值
int rmd = 0;
int len = strlen(b);
int flag = 1;
for(int i=0; i<len; ++i) { // 将 b 对 Phi 取模
rmd = rmd * 10;
if(rmd >= Phi) flag = 0;
rmd = rmd % Phi;
rmd = rmd + (b[i]-'0');
if(rmd >= Phi) flag = 0;
rmd = rmd % Phi;
}
if(flag) // 当 b < Phi
printf("%lld\n", quick_pow(a, rmd));
else printf("%lld\n", quick_pow(a, rmd+Phi));
return 0;
}
相逢是问候：
这是一道非常简单且有意思的题：
有两种操作:
\(1\). \(\forall i\in[l,r],a_i=c^{a_i}\)
\(2\). 求\(\sum_{i=1}^na_i\)
对于此题的修改操作，即是求 \(c\) ^ \(c\) ^ \(\cdots\) ^ \(a_i\) \((\bmod p)\) （此处“^”表示乘方）可以证明当层数足够多时其结果为常数。
所以可以使用势能线段树进行修改，对于每个点的修改利用扩展欧拉定理求解，并统计其修改次数，当其足够多时便不用修改。
但是此时 \(3\log\) 的复杂度还不足以通过此题，可以预处理快速幂从而省去一个 \(\log\) 的复杂度即可。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
ll s=0,k=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-')k=-k;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*k;
}
const int N=1e5+10,M=55;
int n,m,cnt;
ll p,c,a[N],phi[M],op,x,y,Mul1[N][M],Mul2[N][M];
bool fl,f1[N][M],f2[N][M];
struct node{
ll v,mn;
}t[N<<1];
inline ll Phi(ll V){
ll res=V,nq=sqrt(V);
for(register ll i=2;i<=nq;i++){
if(V%i==0){
res=res/i*(i-1);
while(V%i==0) V/=i;
}
}
if(V>1) res=res/V*(V-1);
return res;
}
inline void init(){
ll tmp=p; phi[0]=p;
while(tmp!=1){
tmp=Phi(tmp);
phi[++cnt]=tmp;
}
phi[++cnt]=1;
for(register int i=0;i<=cnt;i++){ //预处理快速幂
Mul1[0][i]=1;Mul2[0][i]=1;
for(register int j=1;j<=10000;j++){
Mul1[j][i]=Mul1[j-1][i]*c;
if(Mul1[j][i]>=phi[i])
Mul1[j][i]%=phi[i],f1[j][i]=1;
f1[j][i]|=f1[j-1][i];
}
f2[1][i]=f1[10000][i];
for(register int j=1;j<=10000;++j){
Mul2[j][i]=Mul2[j-1][i]*Mul1[10000][i];
if(Mul2[j][i]>=phi[i])
Mul2[j][i]%=phi[i],f2[j][i]=1;
f2[j][i]|=f2[j-1][i];
}
}
}
inline ll ksm(ll t,ll Mod){
ll mod=phi[Mod];
ll res,v1=t%10000,v2=t/10000;
fl=0;
res=Mul1[v1][Mod]*Mul2[v2][Mod];
if(res>=mod) res%=mod,fl=1;
else fl=fl|f1[v1][Mod]|f2[v2][Mod];
return res;
}
inline ll dfs(ll V,int deep,int pH){ // 运用扩展欧拉定理求答案 c^c^c...^c^ai
if(deep==pH){
if(V>=phi[deep]) fl=1,V%=phi[deep];
return V;
}
ll B=dfs(V,deep+1,pH);
if(fl) return ksm(B+phi[deep+1],deep);
return ksm(B,deep);
}
inline void pushup(int s){ // 势能线段树（执行足够多次操作后将会是一个固定值）
t[s].v=(t[s<<1].v+t[s<<1|1].v);
if(t[s].v>=p) t[s].v-=p;
t[s].mn=min(t[s<<1].mn,t[s<<1|1].mn);
}
inline void build(int s,int l,int r){
if(l==r){
t[s].v=a[l];
return;
}
int mid=(l+r)>>1;
build(s<<1,l,mid);
build(s<<1|1,mid+1,r);
pushup(s);
}
inline void update(int L,int R,int l,int r,int s){
if(t[s].mn>=cnt) return ;
if(L==R){
++t[s].mn;
fl=0;
t[s].v=dfs(a[L],0,t[s].mn);
return ;
}
int mid=(L+R)>>1;
if((l<=mid)&&(t[s<<1].mn<cnt)) update(L,mid,l,r,s<<1);
if((r>mid)&&(t[s<<1|1].mn<cnt)) update(mid+1,R,l,r,s<<1|1);
pushup(s);
}
inline ll query(int L,int R,int l,int r,int s){
if((l<=L)&&(R<=r)) return t[s].v;
int mid=(L+R)>>1;
ll res=0;
if(l<=mid) res+=query(L,mid,l,r,s<<1);
if(res>=p) res-=p;
if(r>mid) res+=query(mid+1,R,l,r,s<<1|1);
if(res>=p) res-=p;
return res;
}
int main() {
n=read();m=read();p=read();c=read();
for(register int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
init();
while(m--){
int op,x,y;
op=read();x=read();y=read();
if(op==0) update(1,n,x,y,1);
else printf("%lld\n",query(1,n,x,y,1));
}
return 0;
}
exgcd:
\(Bézout\)： 对于任意整数 \(a,b\) 存在一堆整数 \(x,y\) 满足 \(ax+by=\gcd(a,b)\) 。
在 \(\gcd\) 最后当 \(b=0\) 时，显然 \(x=1,y=0\) 满足 \(a\times1+0\times 0=\gcd(a,0)\) 。
若 \(b>0\) ，则 \(\gcd(a,b)=\gcd(b,a\ {\rm mod}\ b)\) 假设有 \(x,y\) 满足 \(bx+(a\bmod b)y=\gcd(b,a\bmod b)\)
\(bx+(a\bmod b)y=bx+(a-b\lfloor\frac{a}{b}\rfloor)y=ay+b(x-\lfloor\frac{a}{b}\rfloor y)\)
\(\therefore x'=y,y'=x-\lfloor\frac{a}{b}\rfloor y\) 可得 \(ax'+by'=\gcd(a,b)\) 成立。
$\therefore $ 其通解可表示为 \(x=x_0+kb,y=y_0-ka\) 。
模板：
代码
int exgcd(int a, int b, int &x, int &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a%b, x, y);
int z = x;
x = y;
y = z - (a/b)*y;
return d; // 返回值是 gcd(a, b);
}
对于一般的方程 \(ax+by=c\) ，当且仅当 \(d\mid c\ (d=\gcd(a,b)\ )\) 时有解。
可以先求出 \(ax+by=d\) 的解 \(x_0,y_0\) 易得 \(ax+by=c\) 的解为 \((c/d)x_0,(c/d)y_0\) 。
$\therefore $ 其通解可表示为 \(x=\frac{c}{d}x_0+k\frac{b}{d},y=\frac{c}{d}y_0-k\frac{a}{d}\)
求逆元： 即 \(ax\equiv 1(\bmod p)\) 求 \(x\)
标签：return,数论,res,bmod,exgcd,int,ll,欧拉,equiv From： https://www.cnblogs.com/classblog/p/18326130\(\because ax\equiv 1(\bmod p),\gcd(a,p)=1\)
\(\therefore ax=1+py\)
\(\therefore ax+p(-y)=1\)
使用 \(exgcd\) 求得 \(x\) 即可。
by ysx