专栏文章

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

nnever_knew
P1072题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqhy68r
此快照首次捕获于
2025/12/04 05:06
3 个月前
此快照最后确认于
2025/12/04 05:06
3 个月前
查看原文
考虑根号算法。
先思考暴力的思路，就是枚举，对每一个满足条件的数都做一次统计，可以骗到 50 分。
C
#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);
    }
}
发现上面的代码执行的次数连整数类型都存不下，所以我们猜测需要根号时间复杂度等。
我们发现很多枚举次数都是不需要的，联想到判断质数时只需枚举到根号，因为除了平方根外，剩下的因数都成对分布在一左一右。
那我们只需枚举到根号，大于根号的因数都用小因数除出来。
C
#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);
    }
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...