E2. Divisible Numbers (hard version)(数论)

E2. Divisible Numbers (hard version)(数论)

easy版本里是枚举x，然后找到$\frac{ab}{gcd(ab,x)}$

显然$y|g$。

因为$ab|xy$，那么令$g=gcd(ab,x),k_{1}g=ab,k_{2}g=x$

$k_1|k_{2}y$，$gcd(k_1,k_2)=1$。因此$k_1|y$

枚举$k_1$的倍数即可找到$y$。

那么对于hard，瓶颈在于找$x$，但是注意到我们的关键是找$gcd(ab,x)$。

那么显然我们可以枚举$ab$的因子，这里我们用$\sqrt{n}$分别枚举$a$的因子$a^{\prime }$，$b$的因子$b^{\prime }$，注意到$10^9$内最大因子个数为$1344$。因此双重循环复杂度完全够。

我们枚举$k_1=a^{\prime }{b}^{\prime }$ ，然后判两个数是否在范围内即可。

#include
using namespace std;
typedef long long ll;

ll i,j,k,n,m,t,a,b,c,d,r1,r2;

int main(){
	cin>>t;
	while(t--){
		cin>>a>>b>>c>>d;
		vector<ll> v1,v2;
		for(i=1;i*i<=a;i++){
			if(!(a%i)){
				v1.push_back(i);v1.push_back(a/i);
			}
		}
		for(i=1;i*i<=b;i++){
			if(!(b%i)){
				v2.push_back(i);v2.push_back(b/i);
			}
		}
		for(auto i:v1)for(auto j:v2){
			k=i*j;
			r1=(a/k+1)*k;
			if(r1>c)continue;
			r2=(b/(a*b/k)+1)*(a*b/k);
			if(r2>d)continue;
			cout<<r1<<' '<<r2<<'\n'; goto z;
		}
		cout<<"-1 -1\n";
		z:;
	}
}
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