Description
BD最近沉迷于数论，她最近在研究最小公倍数和最大公约数，她的老师Z给她留了一个作业：在[x,y]区间中，求两个整数最大公约数是x且最小公倍数是y的个数。
Input
第一行输入一个T(T<=300)，表示有T组数据，接下来输入两个数 x, y(1<=x<=y<=1e6)(含义如题)
Output
输出一行表示答案
Accepted Code
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long x, long long y)
{
if (x < y)
{
swap(x, y);
}
long long rem;
while (y > 0)
{
rem = x % y;
x = y;
y = rem;
}
return x;
}
//x*y==a*b必要
int main()
{
std::ios::sync_with_stdio(false);
int t;
while (cin >> t)
{
while (t--)
{
long long x, y, cnt = 0;
cin >> x >> y;
long long h = x * y;
for (long long a = x; a <= y; a++) //a从区间左端开始向右遍历
{
if (h % a == 0)
{
if (h / a >= x && h / a <= y && gcd(a, h / a) == x) // h/a的大小判断条件不可缺少
{
cnt++;
}
}
}
cout << cnt << endl;
}
}
return 0;
}
解后反思
在这个题目上浪费了较多时间，主要原因是一开始想的是双因素遍历，由a*b=x*y自然容易想到双因素，双重for循环直接导致TLE
其实直接判断一个，另一个也就出来了，通过一些约束条件的限制即可
gcd（a,b）==x 以及x*y/a的值必须要在区间内能够取到