CF1665D GCD Guess 题解

发表于 分类于

本文迁移自洛谷原文。

前置知识：中国剩余定理

我们钦定 ，然后这个 根据辗转相减法就可以变为

所以说，当 是 的倍数的时候，要求 是 的倍数。

我们考虑如何充分利用这个性质。

构造一个数 ，和一个数组 ，发现 中是由好多素数构成的。

我们枚举 ，求 ，记为 。如果 是某个 的倍数，那么就可以得到 。

为什么呢？

首先， 中的数两两互质，所以在 gcd 中互不影响。其次， 是 的倍数，那么就意味着 是 的倍数，所以 ，移项就得到了上面那个式子。

最后发现这就是中国剩余定理的板子，直接套即可。

p.s. 这个 正好处于 和 之间，所以我们选取这些数的积做为模数。

Code:

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define reg register
int rem[29];
int pri[]={2,3,7,11,13,17,19,23,29};
ll n,a[16],m[16],Mi[16],mul=1,X;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return ;}
    exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-y*(a/b);
}
inline void solve(){
	for(int i=1;i<=29;++i){
		cout<<"? "<<i<<' '<<1293938646+i<<endl;
		fflush(stdout);
		int x;cin>>x;fflush(stdin);
		for(int j=0;j<9;++j)if(x%pri[j]==0)rem[j]=pri[j]-(i%pri[j]);
	}
	n=9;mul=1;memset(m,0,sizeof(m));X=0;memset(Mi,0,sizeof(Mi));
    for(int t=1;t<=n;++t){
		m[t]=pri[t-1];
		mul*=m[t];
		a[t]=rem[t-1];
    }
    for(int t=1;t<=n;++t){
		Mi[t]=mul/m[t];
		ll x=0,y=0;
        exgcd(Mi[t],m[t],x,y);
        X+=a[t]*Mi[t]*(x<0?x+m[t]:x);
    }
    cout<<"! "<<X%mul<<'\n';
}
int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	for(;T--;)solve();
	return (0-0);
}