题解：P1072 [NOIP2009 提高组] Hankson 的趣味题

never_knew · 2025-01-16 14:52:36 · 题解

考虑根号算法。

先思考暴力的思路，就是枚举，对每一个满足条件的数都做一次统计，可以骗到 50 分。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int cnt=0;
        for(int i=1;i<=d;i++)
        {
            if(d%i==0)
            {
                if(__gcd(i,a)==b&&i/__gcd(i,c)*c==d) cnt++;
            }

        }
        printf("%d\n",cnt);
    }
}

发现上面的代码执行的次数连整数类型都存不下，所以我们猜测需要根号时间复杂度等。

我们发现很多枚举次数都是不需要的，联想到判断质数时只需枚举到根号，因为除了平方根外，剩下的因数都成对分布在一左一右。

那我们只需枚举到根号，大于根号的因数都用小因数除出来。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int cnt=0;
        for(int i=1;i<=sqrt(d);i++)
        {
            if(d%i==0)
            {
                if(__gcd(i,a)==b&&i/__gcd(i,c)*c==d) cnt++;
                int x=d/i;
                if(x!=i&&__gcd(x,a)==b&&x/__gcd(x,c)*c==d) cnt++;
            }

        }
        printf("%d\n",cnt);
    }
}