CRT板子
注意题目要求ans>d 其实就是减完d再%M+M%M
一开始英文看成了1天输出单数....输出格式还是复制的好
中国剩余定理
给定n组同余方程 形如x≡a[i](mod m[i])的形式 求解x
> Q:没有明显的思路嘤嘤嘤
这个.....那我们拆成不定方程
x = k[i] * m[i] + a[i]
x = k[j] * m[j] + a[j]
然后方程组联立求k[]就好了对不对
（啪！）
(这个方法确实是行的...就是不好写 又叫 合并法)
但是它并不是我们今天要说的Chinese Remainder Theorem
这个是一种解所有m[]互质的特殊情况的算法
换句话说 就是利用
若 n = pq 且 gcd( p , q )= 1 ,那么 x mod p , x mod q 的值确定后, x mod n 的值也会随之确定。
可以O(n*O(gcd))求解
算法流程:
考虑对于每一个m[i] 求一个数t[i]使得
t[i] % m[j] = 0 (j != i)
t[i] % m[j] = 1 (j == i)
这样对于所有的i (1~n)∑t[i]*a[i] 就是答案
(因为t[i]是m[j]的倍数 mod 的时候会消掉)
但是t[i]怎么求呢
考虑先满足第一个条件 我们就求一个rev[i]表示LCM / m[i]
然后求一个rev[i]的倍数 满足mod m[i] == 1
也就是r[i] * x + m[i] * y = 1
这不就是exgcd吗!
最后t[i]就是r[i] * x
至此 就 做完了
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<queue> 6 #include<vector> 7 #define ms(a,b) memset(a,b,sizeof a) 8 #define rep(i,a,n) for(int i = a;i <= n;i++) 9 #define per(i,n,a) for(int i = n;i >= a;i--) 10 #define inf 2147483647 11 #define eps 1e-8 12 using namespace std; 13 typedef long long ll; 14 ll read() { 15 ll as = 0,fu = 1; 16 char c = getchar(); 17 while(c < '0' || c > '9') { 18 if(c == '-') fu = -1; 19 c = getchar(); 20 } 21 while(c >= '0' && c <= '9') { 22 as = as * 10 + c - '0'; 23 c = getchar(); 24 } 25 return as * fu; 26 } 27 const int N = 100005; 28 ll gcd(ll a,ll b) {return b ? gcd(b,a%b) : a;} 29 //head 30 const int M = 21252; 31 ll d; 32 ll a[3],r[3],t[3],m[3] = {23,28,33}; 33 ll exgcd(ll a,ll b,ll &x,ll &y) { 34 if(!b) { 35 x = 1,y = 0; 36 return a; 37 } 38 ll t = exgcd(b,a%b,y,x); 39 y -= (a/b) * x; 40 return t; 41 } 42 int main() { 43 ll y,tot = 0; 44 r[0] = 28*33,r[1]=23*33,r[2]=23*28; 45 rep(i,0,2) { 46 exgcd(r[i],m[i],t[i],y); 47 t[i] = ((t[i]%M)+M)%M; 48 t[i] = r[i] * t[i] % M; 49 } 50 while(1) { 51 scanf("%lld%lld%lld%lld",a,a+1,a+2,&d); 52 if(a[0] == -1 && a[1] == -1 && a[2] == -1 && d == -1) break; 53 ll ans = 0; 54 rep(i,0,2) ans = (ans + t[i] * a[i]) % M; 55 ans = (ans%M+M)%M; 56 if(ans <= d) ans+=M; 57 printf("Case %d: the next triple peak occurs in %lld days. ",++tot,ans-d); 58 } 59 return 0; 60 }