ABC193 E-Oversleeping 题解_abc193e

暴力做法:按题意模拟

正确做法: $EXCRT$

出题人怕人看不出是解同余方程组，专门把柿子糊脸上了(。

根据题意,要找到一个最小时间 $t$ 满足这个方程组:

{      t ≡ i      ( m o d     ( 2 X + 2 Y )   )     ( i ∈ [ X , X + Y ) ) t ≡ j      ( m o d     ( P + Q )   )     ( j ∈ [ P , P + Q ) ) \left\{

$$\begin{matrix} \ \ \ \ t\equiv i\ \ \ \ (mod\ \ \ (2X+2Y)\ )\ \ \ (i\in[X,X+Y))\\ t\equiv j\ \ \ \ (mod\ \ \ (P+Q)\ )\ \ \ (j\in[P,P+Q)) \end{matrix}$$ \right. {    t≡i    (mod   (2X+2Y) )   (i∈[X,X+Y))t≡j    (mod   (P+Q) )   (j∈[P,P+Q))​

虽然 $X$ 和 $P$ 很大,但是 $P$ 和 $Q$ 非常小，因此可以枚举 $[X,X+Y)$ 和 $[P,P+Q)$ 的每一个 $i,j$来解这个方程组。 $2X+2Y$ 和 $P+Q$ 不一定互质，因此需要 $EXCRT$ 合并求解。

没了。

Code

#include<bits/stdc++.h>
#define N 200006
#define LL __int128
#define int long long 
using namespace std;
 
int T,t;
int X,Y,P,Q;
int mod1,mod2;
int a1,a2,b1,b2;
 
inline int qr()
{
	char a=0;int w=1,x=0;
	while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
	while(a<='9'&&a>='0'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
	return w*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 mul(LL a,LL b,LL mod)
{
	LL ans=0;
	for(;b;a=(a+a)%mod,b>>=1)
		if(b&1) ans=(ans+a)%mod;
	return ans;
}
 
LL excrt()
{
    LL x,y,M=b1,ans=a1;
    LL a=M,b=b2,c=(a2-ans%b+b)%b;
    LL gcd=exgcd(a,b,x,y);
    LL bg=b/gcd;
    if(c%gcd!=0) return -1; 
    x=mul(x,c/gcd,bg);
    ans+=x*M;M*=bg;
    ans=(ans%M+M)%M;
    return (ans%M+M)%M;
}
 
signed main()
{
	T=qr();
	while(T--)
	{
		X=qr();Y=qr();
		P=qr();Q=qr();
		b1=(X+Y)<<1ll;
		b2=P+Q;
		LL ans=2e18;
		int opl=0;
		for(register int i=0;i<Y;i++)
			for(register int j=P;j<P+Q;j++)
			{
				a1=i+X;a2=j;
				LL ans1=excrt();
				if(ans1==-1) continue;
				opl=1;
				ans=min(ans1,ans);
			}
		if(opl) printf("%lld\n",(long long)ans);
		else printf("infinity\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77