【Luogu P4777】 扩展中国剩余定理(EXCRT)

先贴代码,解析待填坑。

#include<cstdio>
#include<algorithm>
#define int long long
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
int n,a[100005],b[100005];
int exgcd(int a,int b,int &x,int &y)
{
	if (b==0)
	{
		x=1,y=0;
		return a;
	}
	int ans=exgcd(b,a%b,y,x);
	y-=(a/b)*x;
	return ans;
}
inline ll ksc(ll x,ll y,ll p)
{
    ll z=(ld)x/p*y;
    ll res=(ull)x*y-(ull)z*p;
    return (res+p)%p;
}
signed main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i],&b[i]);
	int GCD,A1,A2,K1,K2,R,x=b[1],LCM;
	for (int i=2;i<=n;i++)
	{
		if (b[i]<b[i-1]) swap(a[i],a[i-1]),swap(b[i],b[i-1]);
		A1=a[i-1],K1,A2=a[i],K2,R=b[i]-b[i-1];
		GCD=exgcd(A1,A2,K1,K2);LCM=A1/GCD*A2;
		K1=(K1%A2+A2)%A2;
		K1=ksc(K1,R/GCD,A2);
		x=(ksc(K1,A1,LCM)+b[i-1])%LCM;
		b[i]=x,a[i]=LCM;
	}
	printf("%lld",x);	
	return 0;
}
上一篇:校赛G题代码backup


下一篇:进制hash应用之查询子串