#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    int n;
    LL x=0;
    cin>>n;
    LL m1,a1;
    cin>>a1>>m1;
    for(int i=0;i<n-1;i++){
        LL a2,m2,k1,k2;
        cin>>a2>>m2;
        LL d=exgcd(a1,a2,k1,k2);
        if((m2-m1)%d){x=-1;break;}
        k1*=(m2-m1)/d;
        k1=(k1%(a2/d)+a2/d)%(a2/d);
        x=k1*a1+m1;
        LL m=abs(a1/d*a2);
        m1=k1*a1+m1;
        a1=m;
    }
    if(x!=-1)x=(m1%a1+a1)%a1;
    cout<<x<<endl;
    return 0;
}

$\color{#FF11FF}{难}$$\color{#4198E1}{度}$$\color{#FF9864}{中}$$\color{#36FF7F}{等}$

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}
int main() {
    int n;
    cin>>n;
    while(n--){
        int a,b,m;
        cin>>a>>b>>m;
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d)cout<<"impossible\n";
        else cout<<(long long)x*(b/d)%m<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}
int main() {
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        int x,y;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quick(int a,int b,int p){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return ans%p;
}
int niyuan(int a,int p){
    if(a%p==0) return -1;
    return quick(a,p-2,p);
}
int main() {
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        if(niyuan(a,b)==-1) cout<<"impossible\n";
        else cout<<niyuan(a,b)<<endl;
    }
    return 0;
}

其实代码也没那么复杂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b,p;
ll quick_power(ll a,ll b,ll c){
    ll ans=1;
    a%=c;
    while(b){
        if(b&1)ans=(ans*a)%c;
        a=(a*a)%c;
        b/=2;
    }
    return ans;
}
int main() {
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b>>p;
        cout<<quick_power(a,b,p)<<endl;
    }
    return 0;
}

法1：对每个数都计算

#include<bits/stdc++.h>
using namespace std;
long long euler(int x){
    long long res=x;
    for(int i=2;i<=x/i;i++)
        if(x%i==0){
            while(x%i==0) x/=i;
            res*=(i-1);res/=i;
        }
    if(x>1) res=res/x*(x-1);
    return res;
}
int main() {
    long long sum=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) sum+=euler(i);
    cout<<sum<<endl;
    return 0;
}

法2：《优秀方法》筛法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+9;
int n,phi[N];
int primes[N],cnt;
bool st[N];
ll get_eulers(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++){
            int t=primes[j]*i;
            st[t]=true;
            if(i%primes[j]==0){
                phi[t]=phi[i]*primes[j];
                break;
            }
            phi[t]=phi[i]*(primes[j]-1);
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++) res+=phi[i];
    return res;
}
int main() {
    cin>>n;
    cout<<get_eulers(n)<<endl;
    return 0;
}

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

我曾经讨厌这种题，那是我是老老实实用循环做的
后来，我学到了递归gcd，代码一下子短了很多
当然了，也可以直接调用__gcd(a,b)
死做的代码我不给了（懒得写）
__gcd(a,b)我也不给了（过于简单）
这是递归代码
证明：辗转相除法
百度 可以搜索
其实你们应该在数学里学过

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(!b) return a;
    return gcd(b,a%b);
}
int main() {
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

我曾经讨厌这种题，那是我是老老实实用循环做的
后来，我学到了递归gcd，代码一下子短了很多
当然了，也可以直接调用__gcd(a,b)
死做的代码我不给了（懒得写）
__gcd(a,b)我也不给了（过于简单）
这是递归代码
证明：辗转相除法
百度 可以搜索
其实你们应该在数学里学过

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(!b) return a;
    return gcd(b,a%b);
}
int main() {
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
int main() {
    int n;
    cin>>n;
    unordered_map<int,int> mp;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
            while(x%i==0){
                x/=i;
                mp[i]++;
            }
        if(x>=2) mp[x]++;
    }
    ll res=1;
    for(auto prime:mp){
        ll a=prime.first,b=prime.second;
        ll c=1;
        while(b--) c=(c*a+1)%MOD;
        res=res*c%MOD;
    }
    cout<<res<<endl;
    return 0;
}