NEFU-1411 GCD&LCM

NEFU-1411 GCD&LCM

/ 0评 / 959次 / 0

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的值必须要在区间内能够取到

发表回复

您的电子邮箱地址不会被公开。

你好 No.65341