欧拉定理：若 gcd(a,n)=1，则 a^φ(n)≡1(mod n)。

【欧拉定理简介】
欧拉定理：若 gcd(a,n)=1，则 a^φ(n)≡1(mod n)。
（1）例如，a=3，n=10，gcd(3,10)=1，φ(10)=4，则 a^φ(n)=3^4=81，81 mod 10=1，欧拉定理成立。
（2）当 n 是质数时，φ(n)=n-1，欧拉定理退化为费马小定理 a^(n-1)≡1(mod n)，其中 a 和 n 的最大公约数 gcd(a,n)=1。 例如，a=2，n=5，gcd(2,5)=1，a^(n-1)=2^4=16，16 mod 5=1，费马小定理成立。
（3）注意：费马小定理是欧拉定理的特例，在模运算中应用广泛。

【算法代码】
该代码实现了四个核心功能：
（1）计算最大公约数 (gcd)；
（2）通过质因数分解计算欧拉函数 φ(n)；
（3）计算快速幂；
（3）验证欧拉定理 a^φ(n)≡1 mod n 的条件和结论。

#include <bits/stdc++.h>
using namespace std;int gcd(int a, int b) {if(b==0) return a;else return gcd(b,a%b);
}int oula_phi(int x) {int ans=x;for(int i=2; i*i<=x; i++) {if(x%i==0) {ans=ans/i*(i-1);while(x%i==0) x/=i;}}if(x>1) ans=ans/x*(x-1);return ans;
}int fastPow(int a,int b,int p) {int ans=1;while(b) {if(b & 1) ans=ans*a%p;a=a*a%p;b>>=1;}return ans%p;
}bool verify_euler_theorem(int a,int n) {if(gcd(a,n)!=1) return false;int phi=oula_phi(n);int ans=fastPow(a,phi,n);return ans==1;
}int main() {int a,n;cin>>a>>n; //gcd(a,n)=1if(verify_euler_theorem(a,n)) {cout<<"φ("<<n<<")="<<oula_phi(n)<<endl;cout<<a<<"^φ("<<n<<")≡1 mod "<<n<<" is true."<<endl;} else cout<<"Not meeting the conditions."<<endl;return 0;
}/*
in:
3 7out:
φ(7)=6
3^φ(7)≡1 mod 7 is true.
*/