不会int128求调
查看原帖
不会int128求调
315205
Kniqht楼主2023/11/5 10:37

可能因为dev版本太老了没法使用int128,所以有没有大佬能帮我看看下面为什么炸了吗?样例输出巨大的数(代码是ll并且用正常输入输出的话,是WA一个点,这个点需要int128)

拜谢

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
ll n;
void read(ll &x){
    char c=0;
    while(c<'0'||c>'9')
		c=getchar();
    while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}	
}
void print(ll x){
    if(x>9) print(x/10);
    putchar('0'+(x%10));
}
ll abs128(ll x){
    return x>0ll?x:-x;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
ll mod(ll a,ll p){
	return ((a%p)+p)%p;
}
signed main(){
	read(n);
	ll a1,m1;
	read(a1);read(m1);
	for(int i=1;i<n;i++){
		ll a2,m2,k1,k2;
		read(a2),read(m2);
		ll d=exgcd(a1,-a2,k1,k2);
		if((m2-m1)%d){
			printf("-1");
			return 0;
		}
		k1=mod(k1*(m2-m1)/d,abs128(a2/d));
		m1=a1*k1+m1;
		a1=abs128(a1/d*a2);
	}
	print((m1%a1+a1)%a1);
	return 0;
}

2023/11/5 10:37
加载中...