公约数（acwing每日一题）

时间：2024-04-04 15:17:35

题目描述：

给定两个正整数 a 和 b。

你需要回答 q个询问。

每个询问给定两个整数 l,r，你需要找到最大的整数 x，满足：

  1. x 是 a 和 b的公约数。
  2. l≤x≤r。

输入格式：

第一行包含两个整数 a,b。

第二行包含一个整数 q。

接下来 q 行，每行包含两个整数 l,r。

输出格式：

每个询问输出一行答案，即满足条件的最大的 x，如果询问无解，则输出 −1。

数据范围：

前六个测试点满足 1≤a,b≤100，1≤q≤20。
所有测试点满足 1≤a,b≤1e9，1≤q≤1e4，1≤l≤r≤1e9。

输入样例：

9 27
3
1 5
10 11
9 11

输出样例：

3
-1
9

分析步骤：

  第一：首先，拿到题目我们就知道我们要求的是公约数，所以我们就得明确我们这道题目一定是要用到辗转相除法和试除法求约数的！这是本题的第一个特点。

  第二：其次，如果你能够知道我们这道题目的范围内一个数最多只有一千多个约数的话，你就可以直接运用暴力求解，也能在规定时间解出这道题目这是本题的第二个特点。

  第三：然后，我们还可以看到我们是要在一个区间之中求出一个最大的约数，如果我们把一个数的所有约数都求出来，在排个序那么他们将单调，所以我们可以在这个约数区间里找到一个数，看看是否在给定的询问区间之中，如果在则更新左区间，不在则更新右区间直到我们找到那个最大的数，至此我们分析出了单调和找到一个点可以将一个区间分为满足和不满足和最值三个部分所以二分的思想就出来了，这是本体的第三个特点。

  第四：书写主函数，构建整体框架：

  • 输入值，并且运用试除法将在这个区间的公约数都给求出来

  • 输入值，进入循环，输入给定的左右两区间。

  • 在定义我们的左右两区间，左边界定义为0，因为约数区间第一个数是从0开始的，右边界定义为cnt-1，因为最后一个数下标是cnt-1。这里一定要明白我们这个二分区间，是二分的哪里的区间我们是要二分求出来的那些公约数的区间，因为我们要首先满足第一个条件，x 是 a 和 b的公约数，看看哪个公约数满足我们的第二个条件，l≤x≤r。

  • 求出mid的值，如果这个值比给定的右边界更小的话就更新一下自己的左边界，因为如果这个数是满足条件的话，那么比它小的数即使也是公约数，但他不是最大的，所以左边的区间已经没有用了，应该在右边找。如果这个值比给定的右边界更大的话，那么我们这个数的约数区间的右边一定比这个数还要大，那么这个数都不可能了，比这个数更大的话就越不可能了。所以更新右区间。

  • 找完一轮后，如果最终的这个值比给定的左边界大于等于的话就是答案，反之则不可能有这个数就输出-1。 

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);

    init_divisors(a, b);

    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int L, R;
        scanf("%d%d", &L, &R);

        int l = 0, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] <= R) l = mid;
            else r = mid - 1;
        }

        if (q[r] >= L) printf("%d\n", q[r]);
        else puts("-1");
    }

    return 0;
}

  第五：书写试除法函数：

  • 这里我们想一下公约数是不是有一个最大的公约数，所有的公约数都只能小于或等于这个公约数，并且这些公约数都必须是最大公约数的约数，所以我们只要把最大的公约数求出来，再在最大公约数的范围之下求我们的遍历次数就会小很多。

  • 所以我们先利用辗转相除法求出最大的公约数。

  • 利用for循环，如果这个i是d的约数的话，就代表这个数也是约数，就把它放入我们的数组。

  • 如果这个数的另一半和自己不一样的话，那么也给它放入我们的约数数组

  • 最后一定要记得排序，二分查找一定是要二分有序的序列。

void init_divisors(int a, int b)
{
    int d = gcd(a, b);

    for (int i = 1; i <= d / i; i ++ )
        if (d % i == 0)
        {
            q[cnt ++ ] = i;
            if (i != d / i) q[cnt ++ ] = d / i;
        }
    sort(q, q + cnt);
}

  第六：暴力求解：

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);

    init_divisors(a, b);

    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int L, R;
        scanf("%d%d", &L, &R);

        int l = 0, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] <= R) l = mid;
            else r = mid - 1;
        }

        if (q[r] >= L) printf("%d\n", q[r]);
        else puts("-1");
    }

    return 0;
}

代码:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1350;

int q[N], cnt;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

void init_divisors(int a, int b)
{
    int d = gcd(a, b);

    for (int i = 1; i <= d / i; i ++ )
        if (d % i == 0)
        {
            q[cnt ++ ] = i;
            if (i != d / i) q[cnt ++ ] = d / i;
        }
    sort(q, q + cnt);
}

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);

    init_divisors(a, b);

    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int L, R;
        scanf("%d%d", &L, &R);

        int l = 0, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] <= R) l = mid;
            else r = mid - 1;
        }

        if (q[r] >= L) printf("%d\n", q[r]);
        else puts("-1");
    }

    return 0;
}

相关文章