Codeforces Round #828 (Div. 3) E1 E2-蒲公英云

Codeforces Round #828 (Div. 3) E1 E2

心已赠人 2024-03-30 13:07 193阅读 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;
}