@[杜岱玮](/space/show?uid=64366) 假啊
by MagicSpark @ 2019-02-23 09:02:36
欧拉定理那么水。。。exgcd也是那么水。。。相比莫比乌斯反演已经十分友好了
by LightningUZ @ 2019-04-14 21:13:10
@[LightningUZ](/space/show?uid=106252) Orz巨佬
by 诱宵美⑨ @ 2019-05-04 21:29:27
@[MagicSpark](/user/75880) ++qwq
顺便附上代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
bool isprime(ll x){
if(x==1)return 0;
for(ll i=2;i*i<=x;i++)if(x%i==0)return 0;
return 1;
}
ll phi(ll n){
ll ret=n;
for(ll i=1;i*i<=n;i++)
if(n%i==0){
if(isprime(i))ret=ret/i*(i-1);
if(isprime(n/i))ret=ret/(n/i)*(n/i-1);
}
return ret;
}
ll qpow(ll a,ll b,ll m){return !b?1:qpow(a*a%m,b>>1,m)*(b&1?a:1)%m;}
int main(){
cin>>a>>b;
cout<<qpow(a,phi(b)-1,b)<<endl;
return 0;
}
```
by Spasmodic @ 2020-02-18 22:27:10
@[LightningUZ](/user/106252) ~~PR求phi了解一下~~
by Spasmodic @ 2020-02-18 22:28:02
@[happydef](/user/121027) ,這個快速冪好短啊
（讚讚讚）
短小精悍！
by RAYMOND_7 @ 2020-04-20 21:42:02