1.两数之积等于 最大公约数和最小公倍数之积
2.折半算提高效率
35ms:
#include <bits/stdc++.h>
using namespace std;
long long n, m, res, op;
int main()
{
cin >> m >> n;
if (m > n)
{
int t = n;
n = m;
m = t;
}
if (m == n)
{
res--;
}
op = sqrt(n * m);
for (long long int i = m; i <= op; i++)
{
long long int l = m * n / i;
if (i * l / __gcd(i, l) == n && __gcd(i, l) == m)
res += 2;
}
cout << res;
}42ms:
#include <bits/stdc++.h>
using namespace std;
long long n, res;
int main()
{
int m;
cin >> m >> n;
if (m > n)
{
int t = n;
n = m;
m = t;
}
for (int i = m; i <= n; i++)
{
int l = m * n / i;
if (i * l / __gcd(i, l) == n && __gcd(i, l) == m)
res += 1;
}
cout << res;
}