Codeforces Round #828 (Div. 3) E1 E2

心已赠人 2024-03-30 13:07 65阅读 0赞

[Problem - E1 - Codeforces][]

[Problem - E2 - Codeforces][]

题意：

给定a,b,c,d，其中 a<x<=c，b<y<=d，问是否存在这样的x，y使得x\*y能被a\*b整除

思路：

E1：

我们去从a+1到c枚举 x ，x\*y能被a\*b整除可以转化为 y能被a\*b/gcd(a\*b,x)整除（这个可以用唯一分解质因数去感性理解，**y 必须包含 a\*b的所有质因子除去x的所有质因子**，所有问题就转化成：去求区间\[b+1,d\]里的a\*b/gcd(a,b)的倍数，那么直接取最靠近右边界的倍数就好了

设s=a\*b/gcd(a\*b,s)

答案就是(d/s)\*s，这里是下取整

注意边界情况，边界如果是s的倍数就直接特判输出

如果区间内不存在s的倍数，就判无解

否则就输出最靠近右边界的倍数

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int a,b,c,d;
    void solve(){
        cin>>a>>b>>c>>d;
        for(int x=a+1;x<=c;x++){
            int s=(a*b)/__gcd(a*b,x);
            if((b+1)%s==0){
                cout<<x<<" "<<b+1<<'\n';
                return;
            }
            if((b+1)/s==d/s){
                continue;
            }
            cout<<x<<" "<<(d/s)*s<<'\n';
            return;
        }
        cout<<-1<<" "<<-1<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

E2：

因为x\*y能被a\*b整除，因此x\*y一定含有a\*b的因子，所以我们去dfs枚举a\*b的所有因子，放到数组里，然后去枚举其中一个因子x，构造另一个因子a\*b/x，去构造超过a的第一个倍数和超过b的第一个倍数就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=4e4+5000;
    vector<pair<int,int> > v;
    map<int,int> mp;
    int a,b,c,d,t,len=0,cnt=0;
    int vis[mxn],prime[mxn],divd[mxn];
    void initd(int n){
    	for(int i=2;i<=n;i++){
    		if(!vis[i]) prime[++len]=i;
    		for(int j=1;prime[j]<=n/i;j++){
    			vis[i*prime[j]]=1;
    			if(i%prime[j]==0) break;
    		}
    	}
    }
    void dfs(int u,int p){
    	if(p>c) return;
    	if(u==v.size()){
    		if((a*b)/p<=d) divd[++cnt]=p;
    		return;
    	}
    	for(int i=0;i<=v[u].second;i++){
    		dfs(u+1,p);
    		p*=v[u].first;
    	}
    }
    void init(){
    	len=0,cnt=0;
    	mp.clear();v.clear();
    	memset(divd,0,sizeof(divd));
    }
    void solve(){
    	init();
    	cin>>a>>b>>c>>d;
    	t=a;
    	for(int i=1;prime[i]<=t/prime[i];i++){
    		int p=prime[i];
    		if(t%p==0){
    			while(t%p==0) t/=p,mp[p]++;
    		}
    	}
    	if(t>1) mp[t]++;
    	t=b;
    	for(int i=1;prime[i]<=t/prime[i];i++){
    		int p=prime[i];
    		if(t%p==0){
    			while(t%p==0) t/=p,mp[p]++;
    		}
    	}
    	if(t>1) mp[t]++;
    	for(auto it:mp) v.push_back(it);
    	dfs(0,1);
    	int p=-1,q=-1;
    	for(int i=1;i<=cnt;i++){
    		int x=divd[i],y=(a*b)/x;
    		x=(a/x+1)*x;
    		y=(b/y+1)*y;
    		if(x<=c&&y<=d){
    			p=x,q=y;
    		}
    	}
    	cout<<p<<" "<<q<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	initd(mxn);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

**总结：**

**a\*b能被x\*y整除，可以转化为：y能被a\*b/gcd(a\*b,x)整除**

**数据范围过大时可以dfs枚举因子，这样枚举的复杂度就是因子的数量**

[Problem - E1 - Codeforces]: https://codeforces.com/contest/1744/problem/E1
[Problem - E2 - Codeforces]: https://codeforces.com/contest/1744/problem/E2