489div2-Problem B

Revision en1, by zys23736748, 2018-06-19 05:21:49

给定gcd和lcm反求a和b;

坑比较多,卡了这题,很闹心。 一是题读错了,忘了考虑gcd=lcm的情况。 二是有gcd与lcm不成一对,本身就不存在的情况。

最终改完的代码如下:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define MAXN 100000 + 5

long long x,y,mul;
long long l,r;
long long ans;

int main() {

    cin>>l>>r>>x>>y;
    if(x == y &&  x>=l && x<=r ) {
        cout<<"1"<<endl;
        return 0;
    }

    mul = x*y ;
    long long maxx=y/x;
    long long sqr=sqrt(mul);

    ans = 0;
    if(y % x ==0) {
        for(long long ga=1; ga * ga <= maxx; ga++) {
            if(maxx % ga == 0) {
                long long gb = maxx/ga;
                if(ga*x>=l&&ga*x<=r
                 &&gb*x>=l&&gb*x<=r
                 &&__gcd(ga,gb) == 1 
                 && gb > ga)
                    ans++;
            }
        }
        cout<<ans*2<<endl;
    } 
    else {
        cout<<"0"<<endl;
    }
    return 0;
}

找到了一个比较简洁的实现。 首先把合适的a和b存入vector,然后再运算一次即可。

虽然实现速度不如上面的代码,但是好在能避开很多坑。 尤其最后的判断条件直接用了a*b/gcd(a,b)=y;

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define MOD 1000000007

using namespace std;

ll l, r, x, y, d;
set<ll> uf;

bool good(ll i) {
    return (i >= l && i <= r);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> l >> r >> x >> y;
    d = x*y;
    int ans = 0;
    for(ll i=1; i*i<=y; i++) {
        if(y % i == 0) {
            uf.insert(i);
            uf.insert(y / i);
        }
    }
    for(auto a : uf) {
        for(auto b : uf) {
            if(good(a) && good(b) && __gcd(a,b) == x && a*b/__gcd(a,b) == y) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English zys23736748 2018-06-19 05:21:49 1771 Initial revision (published)