头像

Expelliarmus2011




离线:7小时前


最近来访(29)
用户头像
mayu666
用户头像
听雨家族--无尘Txc.
用户头像
天才小笼包
用户头像
纵横
用户头像
incra
用户头像
关注whale77
用户头像
酷炫
用户头像
maro
用户头像
小霖霖
用户头像
pccc
用户头像
hema5177
用户头像
魔法学徒
用户头像
peipeizhu
用户头像
风未动幡未动
用户头像
用户头像
Pretharp
用户头像
walkerㅤ
用户头像
Renaissance_0
用户头像
sknnn
用户头像
Enemy


#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;
}


活动打卡代码 AcWing 878. 线性同余方程

$\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;
}


活动打卡代码 AcWing 876. 快速幂求逆元

#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;
}


活动打卡代码 AcWing 875. 快速幂

其实代码也没那么复杂

#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;
}


活动打卡代码 AcWing 873. 欧拉函数

#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;
}


活动打卡代码 AcWing 872. 最大公约数

我曾经讨厌这种题,那是我是老老实实用循环做的
后来,我学到了递归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;
}


活动打卡代码 AcWing 871. 约数之和

#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;
}