NOIP2009 - Hankson 的趣味题

【LuoguP1072】【NOIP2009】Hankson 的趣味题
题目链接: https://www.luogu.org/problemnew/show/P1072

引言

半个月没更新博客了, 一直忙于做题练习和学文化课, 不然快被劝退了

最近学习一本通提高篇, 复习下之前学的GCD等数论知识

分析

先从题目描述说起, 给出了a0, a1, b0, b1四个数

求 $ gcd(x, a0) = a1 $ 且 $ lcm(x, b0) = b1 $ 中 x 的方案数

那么首先我们都知道两个很基础的东西

$$ gcd(a, b) = gcd(b, a\mod b) $$

$$ lcm(a, b) = a × b / gcd(a, b) $$

然后就可以来做这道题了

因为

$$ lcm(x, b0) = x × b0 / gcd(x, b0) = b1 $$

所以

$$ x = \frac{b1}{b0} × gcd(x, b0) $$

我们设一个数 $ y = gcd(x, b0) $ 那么一定 $ 1 ≤ y ≤ \sqrt{b0} $

所以我们只要枚举 y 的值, 然后代入算出 $ x = b1 / b0 × y $

然后代入题目中的两个式子进行判断

还有一个简化

$$ x × b0 / gcd(x, b0) == b1 $$

可简化为

$$ b1 / b0 × y × b0 / gcd(x, b0) == b1 $$

即

$$ gcd(x, b0) == y $$

要判断 $ x = b1 / y $ 的情况, 也有可能是一个解

也不要忘了特判 $ y = \sqrt{b0} $ 的情况

然后就完美解决了

代码

没有开各种优化, 能过

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
int n, a0, a1, b0, b1, ans, tmpx, tmpq;
int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}
int main() {
    cin >> n;
    while(n--) {
        cin >> a0 >> a1 >> b0 >> b1;
        ans= 0;
        for(int i= 1; i < sqrt(b0); i++) {
            if(b0 % i == 0) {
                tmpx= b1 / b0 * i;
                if(gcd(tmpx, a0) == a1 && gcd(tmpx, b0) == i) ++ans;
                tmpx= b1 / i;
                if(gcd(tmpx, a0) == a1 && gcd(tmpx, b0) == b0 / i) ++ans;
            }
        }
        tmpq= sqrt(b0);
        if(tmpq * tmpq == b0) {
            tmpx= b1 / b0 * tmpq;
            if(gcd(tmpx, a0) == a1 && gcd(tmpx, b0) == tmpq) ++ans;
        }
        cout << ans << endl;
    }
    return 0;
}

2020-01-11

LuoguP3695 - CYaRon!语

题解

NOIP2009 - Hankson 的趣味题

引言

分析

代码

评论

目录

链接

分类

标签云

最新文章

归档

标签

最新文章

归档

标签

Your browser is out-of-date!