ZackofZHOU @ 2023-07-12 15:49:40
蒟蒻开了氧气，80分
//代码
#include<iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
if(b == 0)
return a;
return gcd(b,a % b);
}
int main()
{
int a,b,ans = 0,num = 0;
cin >> a >> b;
if(a == b)
{
cout << 1;
return 0;
}
for(int i = 1;i <= b;i++)
{
for(int j = i + 1;j <= b;j++)
if(i * j == a * b && gcd(i,j) == a)
ans++;
}
cout << ans * 2;
return 0;
}by ZackofZHOU @ 2023-07-12 15:54:21
帮蒟蒻拿100分，赏一关注！
by WYZ20030051 @ 2023-07-12 16:07:02
虽然但是，1e5的数据你打双重循环肯定过不了
by WYZ20030051 @ 2023-07-12 16:10:11
首先，你只需要一重循环，用O(n)的时间过这道题，暴力枚举肯定过不了
#include <bits/stdc++.h>
using namespace std;
int x,y;
inline int gcd(int x,int y)
{
if(y==0) return x;
return gcd(y,x%y);
}
int main()
{
cin>>x>>y;
int ans=0;
for(int i=1;i<=sqrt(x*y);i++)
{
if(x*y%i==0&&gcd(i,x*y/i)==x) ans++;
}
cout<<ans*2;
return 0;
}by WYZ20030051 @ 2023-07-12 16:10:31
你的思路不对
by ZackofZHOU @ 2023-07-13 14:05:41
蒟蒻两层也可以了
#include<iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
if(b == 0)
return a;
return gcd(b,a % b);
}
int main()
{
int a,b,ans = 0,num = 0;
cin >> a >> b;
if(a == b)
{
cout << 1;
return 0;
}
if(a == 1)
{
cout << 2;
return 0;
}
if(a * a == b)
{
cout << 1;
return 0;
}
for(int i = a;i <= b;i++)
{
if(b % i == 0)
for(int j = i + 1;j <= b;j++)
if(b % j == 0)
if(i * j == a * b && gcd(i,j) == a)
ans++;
}
cout << ans * 2;
return 0;
}by ZackofZHOU @ 2023-07-13 14:08:47
@WYZ20030051 你那段好像没有if(a==b){cout<<1;return 0;的特判，蒟蒻试过了
by WYZ20030051 @ 2023-07-13 14:14:45
@ZackofZHOU 你这样打；两层也可以，但确确实实是有点麻烦了，并且时间复杂度能过但不优
by ZackofZHOU @ 2023-07-13 14:23:38
@WYZ20030051 请dalao解释一下您的代码原理please
by WYZ20030051 @ 2023-07-13 14:31:58
@ZackofZHOU 两个数的最大公约数和最小公倍数的乘积就是这两个数的乘积，有了这个定理后直接枚举最大公约数或最小公倍数就行了，而且题解里有些讲的会更清楚，你可以参考题解
by ZackofZHOU @ 2023-07-13 14:37:11
@WYZ20030051 谢dalao