给定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;
}