首页 > 其他分享 >洛谷题单指南-数学基础问题-P1072 [NOIP2009 提高组] Hankson 的趣味题

洛谷题单指南-数学基础问题-P1072 [NOIP2009 提高组] Hankson 的趣味题

时间:2024-04-11 18:12:51浏览次数:31  
标签:gcd 洛谷题 NOIP2009 long a1 枚举 b0 b1 P1072

原题链接:https://www.luogu.com.cn/problem/P1072

题意解读:求有多少个x,满足x和a0​ 的最大公约数是a1​,x和b0​的最小公倍数是b1,多组数据。

解题思路:

枚举法:

因为x和a0​ 的最大公约数是a1​,x和b0​的最小公倍数是b1,所以x不大于b1​。

枚举x有两种思路:

1、x是a1的倍数,最多需要枚举b1/a1次,如果a1=1,最多b1次,10^9规模,有2000组数据,超时。

2、x是b1的因数,最多需要枚举sqrt(b1)次,也就是x * x <= b1即可,10^4规模,2000组数据,可行。

因此,可以枚举b1的因数,每次枚举可以得到两个因数:x、b1/x,进行判断即可。

100分代码:

#include <bits/stdc++.h>
using namespace std;

long long n, a0, a1, b0, b1;

long long gcd(long long a, long long b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main()
{
    cin >> n;
    while(n--)
    {
        int ans = 0;
        cin >> a0 >> a1 >> b0 >> b1;
        for(long long x = 1; x * x <= b1; x++) //枚举b1的所有因子,每次可以考察i、b1/i两个,循环次数sqrt(b1)
        {
            if(b1 % x == 0)
            {
                if(gcd(x, a0) == a1 && x * b0 == gcd(x, b0) * b1)
                {
                    ans++;
                }
                long long y = b1 / x;
                if(x == y) continue;
                if(gcd(y, a0) == a1 && y * b0 == gcd(y, b0) * b1)
                {
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

注意gcd()的判断前提是x是b1的因子,实际的因子数2*10^9也只有110个,所以gcd的调用复杂度可以忽略,总体复杂度就是10^7规模。

标签:gcd,洛谷题,NOIP2009,long,a1,枚举,b0,b1,P1072
From: https://www.cnblogs.com/jcwy/p/18129799

相关文章

  • 洛谷题单指南-数学基础问题-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
    原题链接:https://www.luogu.com.cn/problem/P1029题意解读:已知x,y,求有多少对p、q,使得p、q的最大公约数为x,最小公倍数为y。解题思路:枚举法即可。枚举的对象:枚举p,且p必须是x的倍数,还有p<=yq的计算:q=x*y/p,q要存在,必须x*y%p==0,且gcd(p,q)==x100分代码:#include......
  • 洛谷题单指南-数学基础问题-P1835 素数密度
    原题链接:https://www.luogu.com.cn/problem/P1835题意解读:要计算L-R范围内素数的个数。解题思路:直接对L~R的每个数判断素数肯定不可取,因为L、R的范围较大。既然要计算素数的个数,那么可以把其中的合数标记出来即可。如何标记合数?可以借助于筛素数的算法思想,枚举每一个素数,然......
  • 洛谷题单指南-数学基础问题-P3383 【模板】线性筛素数
    原题链接:https://www.luogu.com.cn/problem/P3383题意解读:素数筛模版题。解题思路:素数筛介绍所谓素数(质数),是指除了1和它本身以外不再有其他因数的自然数,一般用试除法判断素数(时间复杂度:O(sqrt(n))):boolisprime(intx){if(x<=1)returnfalse;for(inti=2;i*......
  • 洛谷题单指南-数学基础问题-P2926 [USACO08DEC] Patting Heads S
    原题链接:https://www.luogu.com.cn/problem/P2926题意解读:有n个数,计算每个数能整除其他数的个数。解题思路:a[100005]记录所有的数,h[1000005]记录所有数的个数,cnt[1000005]记录所有数能整除其他数的个数只需要读入a数组,同时更新h[a[i]]++再依次从小到大遍历h的下标每一个数i,如......
  • 洛谷题单指南-数学基础问题-P2638 安全系统
    原题链接:https://www.luogu.com.cn/problem/P2638题意解读:把a个红球、b个黑球放入n个盒子,求所有的方法。解题思路:盒子中可以放也可以不放,可以放任意个,因此,题目可以转化为将i个红球(0<=i<=a),j个黑球(0<=j<=b)放入n个盒子的方案数之和,设f(n,i,j)表示将一个红球、j个黑球放入n......
  • 洛谷题单指南-数学基础问题-P3913 车的攻击
    原题链接:https://www.luogu.com.cn/problem/P3913题意解读:车所在的行、列一共有多个个格子。解题思路:假设3*3的棋盘,有三个车分析得知,三个车覆盖了第1、2两行,第2、3两列,覆盖的格子数用公式计算就是2*3+2*3-2*2=8也就是两行格子数加两列格子数再减去交叉点。因此......
  • C++ [NOIP2009 普及组] 分数线划定
    文章目录一、题目描述[NOIP2009普及组]分数线划定题目描述输入格式输出格式样例#1样例输入#1样例输出#1提示二、参考代码一、题目描述[NOIP2009普及组]分数线划定题目描述世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才,A市对所......
  • 洛谷题单指南-数学基础问题-P2789 直线交点数
    原题链接:https://www.luogu.com.cn/problem/P2789题意解读:n条直线可以形成不同交点数的方案数。解题思路:对于n=1、2、3、4的情况进行模拟:n=1时,有1种不同的交点数n=2时,有2种不同的交点数n=3时,有3种不同的交点数n=4时,有5种不同的交点数对n=4的情况,分情况讨......
  • 洛谷题单指南-数学基础问题-P1866 编号
    原题链接:https://www.luogu.com.cn/problem/P1866题意解读:N个整数M1~Mn,对每个整数Mi,选取1~Mi之间的一个数,使得N个数都不一样的选法。解题思路:将M1~Mn由小到大排序,第1个的选法有M1种第2个的选法有M2-1种第3个的选法有M3-2种......第n个选法有Mn-n+1种全部相乘取模即可。......
  • 洛谷题单指南-数学基础问题-P1017 [NOIP2000 提高组] 进制转换
    原题链接:https://www.luogu.com.cn/problem/P1017题意解读:负进制数的转换。解题思路:下面给出两种思路1、枚举法从数据范围来看,∣n∣≤37336,因此,可以对该r进制的数进行枚举,每一次枚举,都计算r进制数对应的十进制数是否和n相等,相等则输出该r进制数。主要问题就是要解决r进制......