首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >洛谷1072(gcd的运用)

洛谷1072(gcd的运用)

作者头像
ACM算法日常
发布2019-01-23 16:37:10
5020
发布2019-01-23 16:37:10
举报
文章被收录于专栏:ACM算法日常ACM算法日常

已知正整数a0,a1,b0,b1,设某未知正整数x满足:

1. x 和 a0 的最大公约数是 a1;

2. x 和 b0 的最小公倍数是b1。

Hankson 的“逆问题”就是求出满足条件的正整数x。但稍加思索之后,他发现这样的x 并不唯一,甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。

输入格式:

第一行为一个正整数 n,表示有 n 组输入数据。接下来的 n 行每行一组输入数据,为四个正整数 a0,a1,b0,b1,每两个整数之间用一个空格隔开。输入数据保证 a0 能被 a1 整除,b1 能被 b0 整除。

输出格式:

共 n 行。每组输入数据的输出结果占一行,为一个整数。

对于每组数据:若不存在这样的 x,请输出 0;

若存在这样的 x,请输出满足条件的x的个数;

输入样例#1:

2 
41 1 96 288 
95 1 37 1776 

输出样例#1:

6 
2

【说明】

第一组输入数据,x可以是 9,18,36,72,144,288,共有 6 个。

第二组输入数据,x可以是48,1776,共有 2 个。

【数据范围】

对于 50%的数据,保证有 1≤a0,a1,b0,b1≤10000 且n≤100。

对于 100%的数据,保证有 1≤a0,a1,b0,b1≤2,000,000,000 且 n≤2000。

NOIP 2009 提高组 第二题

学习大佬的思路~

首先纸上用数学语言写一下题面即:gcd(x, a0) = a1; lcm(x, b0) = b1;

然后按照gcd的常用套路变换一下可知gcd(x / a1, a0 / a1) = 1(想一想,为什么? ——刘汝佳)。而lcm即为x * b0 / gcd(x, b0) = b1,做一下等式变换,把gcd放左边,剩下的一坨归在右边。接着使用同样的套路可得gcd(b1 / x, b1 / b0) = 1。

那么x为b1的约数,就可以√b1去枚举了,同时满足上述两个条件即可。记得枚举x的时候b1 / x也顺便判断一下,以及不可以用a1的倍数去枚举x,因为有些x虽然不是a1的倍数,但b1 / x却是,会漏。

看代码就懂了:

#include <cstdio>
#include <algorithm>
#define R(x) scanf("%d", &x)
#define W(x) printf("%d\n", x)
using namespace std;

int main() {
    int T, a0, a1, b0, b1;
    for (R(T); T; T--) {
        R(a0), R(a1), R(b0), R(b1);

        int ans = 0;
        int p = a0 / a1, q = b1 / b0;//这两个是确定的常量,不妨用符号替代掉

        for (int x = 1; x * x <= b1; x++)
            if (b1 % x == 0) {//如果x是b1的约数
                if (x % a1 == 0 && __gcd(x / a1, p) == 1 && __gcd(b1 / x, q) == 1)
                    ans++;

                int y = b1 / x;//再求和x对应的另一个约数是否符合条件
                if (x == y)
                    continue;

                if (y % a1 == 0 && __gcd(y / a1, p) == 1 && __gcd(b1 / y, q) == 1)
                    ans++;
            }

        W(ans);
    }
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-01-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档