ABC193-E.Oversleeping(中国剩余定理)

前言：

这题是我第一道excrt的题目。题目推半天推出一个exgcd的式子，然后发现需要求两个未知数皆大于0的解。不太会。今天看到题解发现竟然就是一个excrt的板子题.有了excrt的前置知识我们就来做一下这个题.

题目大意:

有两个循环出现的时段，第一个范围为：$[k(2x+2y)+x,k(2x+2y)+x+y),k\ge 0$，第二个范围是$[c(P+Q)+P,c(P+Q)+P+Q)$.现在问你是否存在一个时刻使得同时属于两个时段?

$x,P\le 1e9$
$y,Q\le 500$

题目思路：

容易发现两个时段的长度最大为$500$.暴力枚举两个时段里的点是可以接受的。 假设这两个时刻为$i,j$(相对线段位置来说)。那么我们假设这个时刻为$t$.下式必须被满足:

{ t ≡ x + i   ( m o d    ( 2 x + 2 y ) ) t ≡ P + j   ( m o d    ( P + Q ) ) \left\{

$$\begin{array}{cl} t\equiv x+i \ (mod \ \ (2x+2y))\\ \\ t\equiv P+j \ (mod \ \ (P+Q))\\ \end{array}$$ \right. ⎩⎨⎧​t≡x+i (mod  (2x+2y))t≡P+j (mod  (P+Q))​

这就是一个 excrt的板子题了吧.

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
ll a[5] , b[5];
//快速乘
ll mul(ll a,ll b,ll mod)
{
    ll res=0;
    while(b)
    {
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = exgcd(b, a % b, x, y);
  ll t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
ll excrt(ll n , ll ai[] , ll bi[])
{
    ll x,y;
    ll M=bi[1] , ans=ai[1];//第一个方程的解特判
    for(int i=2;i<=n;i++)
    {
        ll a=M , b=bi[i] , c=(ai[i]-ans%b+b)%b;//ax≡c(mod b)
        ll gcd=exgcd(a,b,x,y) , bg=b/gcd;
        if(c%gcd != 0) return -1; //判断是否无解
        x = mul(x,c/gcd,bg);
        ans += x * M;//更新前k个方程组的答案
        M *= bg;//M为前k个m的lcm
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}
int main()
{
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--){
        ll x , y , p , q; cin >> x >> y >> p >> q;
        ll ans = 7e18;
        for (int i = x ; i < x + y ; i++){
            for (int j = p ; j < p + q ; j++){
                a[1] = i , b[1] = 2 * (x + y);
                a[2] = j , b[2] = p + q;
                ll res = excrt(2 , a , b);
                if (res == -1) continue;
                ans = min(ans , res);
            }
        }
        if (ans == 7e18) cout << "infinity" << endl;
        else cout << ans << endl;
    }
    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