P1072 Hankson 的趣味题

题目描述

题目链接

思路

这道题目的思路题解里说的比较明确，在这里就不在赘述，但是在读题的时候我却漏了一个很重要的条件，实在不应该。

一位大佬的题解

首先题解让我知道的一个比较显然的结论

\[k=\gcd(a,b)\]

\[gcd(\frac{a}{k},\frac{b}{c})=1\]

这个比较显然，因为 \(k\) 是 \(a\) 和 \(b\) 的最大公约数，如果同除这个最大公约数，他们肯定就没有除 \(1\) 外的公约数了，如果有，就可以在上面的 \(k\) 上再乘上这个数，变为新的最大公约数。

\[\left\{\begin{array}{l}{\operatorname{gcd}\left(x / a_{1}, a_{0} / a_{1}\right)=1} \\ {g c d\left(b_{1} / b_{0}, b_{1} / x\right)=1}\end{array}\right.\]

因为在第一个式子中有 \(x/a_1\) 所以 \(x\) 必须是 \(a_1\) 的倍数，又因为在第二个式子中有 \(b_1/x\) 所以 \(x\) 必须为 \(b_1\) 的因子，所以我们就可以 \(\sqrt b_1\) 枚举因子，然后判断了。

Code

#include<bits/stdc++.h>
#define ll long long
inline ll gcd(ll a,ll b) {return b==0 ? a:gcd(b,a%b);}
int n;
int main()
{
    scanf("%d",&n);
    while (n--)
    {
        ll a0,a1,b0,b1,ans=0;
        scanf("%lld%lld%lld%lld",&a0,&a1,&b0,&b1);
        for (ll i=1;i*i<=b1;i++)
        if (b1%i==0)
        {
            if (i%a1==0&&gcd(b1/b0,b1/i)==1&&gcd(i/a1,a0/a1)==1) ans++;
            ll now=b1/i;
            if (now%a1==0&&gcd(b1/b0,b1/now)==1&&gcd(now/a1,a0/a1)==1&&i*i!=b1) ans++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

教训

这道题所用到的知识点都是自己学过的，而且总体的难度也不算太大，可是自己却没有做出来，应该是对学习的东西理解不深，不能灵活运用。

看题目的时候一定要仔细，不要忽略条件。