这个做法是正确的,但复杂度是 $O(n^2logn)$ 的,无法通过本题
你可以尝试枚举 $y$ 的因数
by CloudyKai @ 2023-11-16 18:48:53
```cpp
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b) {
if(b==0) {
return a;
}
else {
return gcd(b,a%b);
}
}
int lsm(int a,int b) {
return (a*b)/gcd(a,b);
}
int main() {
int x,y,ans=0;
cin>>x>>y;
for(int i=x;i<=y;i+=x) {
for(int j=x;j<=y*x/i;j+=x) {
if(gcd(i,j)==x&&lsm(i,j)==y) ans++;
}
}
cout<<ans;
return 0;
}
```
加个约束条件及枚举x的因数
by zyc232008 @ 2023-11-21 17:29:52
@[CloudyKai](/user/301777) 感谢
by shumu @ 2023-11-30 16:52:04