关于本题不懂的地方
查看原帖
关于本题不懂的地方
793625
Pink_Cut_Tree楼主2024/8/10 10:30
#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define ll long long
int x,y,d; 
ll n;
void exgcd(int a,int b,int &x,int &y){
    if(!b){
    	d=a,x=1,y=0;
	} 
    else{
    	exgcd(b,a%b,y,x),y-=a/b*x;
	} 
}
int lcm(int a,int b){
    return a/__gcd(a,b)*b;
}
int m1,r1,m2,r2;
void merge(){
    exgcd(m1,m2,x,y); //求出一组 x,y 的可行解,此时 d 是 m1 和 m2 的 gcd 
    int c=r2-r1; 
    if(c%d){
    	cout<<"-1"; exit(0);
	} 
	int p2=m2/d; 
    x=(x*c/d+p2)%p2;
    int mod=lcm(m1,m2);
    r1=(m1*x+r1+mod)%mod; 
    m1=mod;
}
signed main(){
    cin>>n; //使用 __int128 的抽象操作 
    for(int i=1;i<=n;i++){
        ll a,b; 
        cin>>a>>b;
		m2=a,r2=b; 
        if(i>1){ //不是第一组数据可以 merge 
        	merge();
		} 
        else{
        	m1=m2,r1=r2; //此时的 m1 和 r1 是刚才读进来的 a 和 b
		} 
    }
    ll ans=r1%m1; //__int128 不是不能直接输出嘛,看我转 long long 再输出 
    cout<<ans;
return 0;
}

这几行是什么意思?

int p2=m2/d; 
x=(x*c/d+p2)%p2;
int mod=lcm(m1,m2);
r1=(m1*x+r1+mod)%mod; 
m1=mod;
2024/8/10 10:30
加载中...