首页 > 其他分享 >P1072 [NOIP2009 提高组] Hankson 的趣味题

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

时间:2023-11-10 09:00:28浏览次数:39  
标签:约数 gcd int 质数 NOIP2009 sqrt 质因数 P1072 Hankson

/*
    "爆int, 爆int, 你就会爆int了是吧"
    还是挺难的一道题
    
    具体思路就是通过求出b1的所有约数, 然后看看其中有几个满足gcd(a0, x) == a1 && lcm(b0, x) == b1的数x
    通过上一题其实可以求出来, 在int范围内一个数的约数数量最多只有1600个
    lcm可以通过 a * b / gcd(a, b)的方式求出来, gcd的时间复杂度是O(logn) (实际上很小, 可以估计为10以内的常数)
    也就是说判断一个约数是否满足条件只需要1600 * logn的时间即可, 一共2k个数据, 判断约数最多最多也就3e6 * logn
    这里的logn会在10以内, 总体也就是3e7左右, 看起来很大但实际上每个数的约数数量远不到1600, gcd的logn非常小
    实际运行很快
    
    那么问题就来到了找b1约数上了
    我们可以通过分解b1的质因数, 通过质因数拼凑出所需要的约数(因为最多也就1600个约数, 直接dfs就行, 因为最多搜1600次)
    
    那么问题就到了分解b1的质因数上了
    因为朴素分解质因数是O(sqrt(n))的时间这里也就是5e4乘上2000 大概1e8大概率直接爆掉
    所以要优化一下, 这里只枚举质数即可, 时间上就会从O(sqrt(n)) 变成O(sqrt(n) / ln(sqrt(n))) ([1, n]内大约有n / lnn个质数 —— 质数定理)
    时间上呢?拿计算器算一下sqrt(n)大概是5e4, ln(5e4) 大概是10 那么时间就会变成 5e4 / 10 * 2000 = 1e7 这个就稳多了
    大概优化了10倍, 就可以过掉了
    
    然后问题就到了怎么求质数了
    我们朴素分解质因数只会用到1 - sqrt(n)的数, 那么质数的话就是1 - sqrt(n)内的质数
    sqrt(n) 约等于 5e4很快可以过掉
    
    至此本题结束
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 10001, M = 50010, K = 2e9;

int n;
int primes[M], cnt, cnts; // 线性筛使用
bool st[M];
PII ans[10]; // 每个b1分解的质因数及其个数, 不同的质因数最多只有9个
int ys[1601], ycnt; // 约数 最多1600个

int gcd(int a, int b)
{
    return a ? gcd(b % a, a) : b;
}

int lcm(int a, int b)
{
    return 1ll * a * b / gcd(a, b); // 这里可能会爆int, 藏的很深
}

int qmi(LL a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res *= a;
        a *= a;
        k >>= 1;
    }
    return res;
}

void dfs(int u, int sum) // 求出约数 有一说一 这种方式求真的好好用
{
    if (u > cnts)
    {
        ys[ ++ ycnt] = sum;
        // cout << sum << endl;
        return ;
    }
    
    for (int i = 0; i <= ans[u].y; i ++ ) // 注意是ans[u], 不是ans[i]
        dfs(u + 1, sum * qmi(ans[u].x, i)); // 这里是i次幂不要搞错了 
}

void init(int n)
{
    for (int i = 2; i <= n; i ++ ) // 筛出用到的质数
    {
        if (st[i] == 0) primes[ ++ cnt] = i; // , cout << i << endl;
        for (int j = 1; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int T;
    cin >> T;
    init(M - 1);
    
    
    while (T -- )
    {
        int x, y, a, b, n;
        scanf("%d%d%d%d", &x, &y, &a, &b);
        cnts = 0;
        ycnt = 0;
        n = b; // 这里不能直接用b, 因为下面还会用到b, (分解n的质因数会消掉n) 
        for (int i = 1; primes[i] <= n / primes[i]; i ++ ) // 分解质因数 2e9也就用到sqrt(2e9)里面的质数, 后面的质数可以和前面的一一对应, 所以只用前1e5个质数就足够了
        {
            int v = primes[i];
            if (n % v == 0) // 朴素分解质因数板子, 不过这里通过只筛质数, 优化了一下
            {   
                int s = 0;
                cnts ++ ;
                while (n % v == 0) n /= v, s ++ ;
                ans[cnts] = {v, s};
            }
        } // 为什么可以通过dfs暴力求质数? 在int范围内的数, 最多可以分出9个不同的质因数emm, 而b的约数可以通过它的质因数拼凑出来, 就可以了
        if (n != 1) ans[ ++ cnts] = {n, 1};
        dfs(1, 1);
        int res = 0;
        for (int i = 1; i <= ycnt; i ++ )
        {
            int k = ys[i];
            if (gcd(x, k) == y && b == lcm(a, k)) res ++ ;  // 虽然k是b的约数, 但是它和a的最小公倍数不一定是b, lcm(4, 6) == 12, 6是12的约数, but, lcm(6, 6) == 6
        }
        
        printf("%d\n", res);
    }
    
    return 0;
}

标签:约数,gcd,int,质数,NOIP2009,sqrt,质因数,P1072,Hankson
From: https://www.cnblogs.com/blind5883/p/17823328.html

相关文章

  • 学习记录:NC16622[NOIP2009]多项式输出
    题目链接:https://ac.nowcoder.com/acm/problem/16622解题思路:这题有个在拓扑序上的直觉。(并不完全是拓扑学,只是一种感觉)举个例子,每i项,都是有了符号,再有系数,最后指数,我们确定了前面输出什么才有后面的判断。但并不完全是这样,该题当指数为0时,会影响系数的输出格式(x是否要输出......
  • [NOIP2009 普及组] 分数线划定
    [NOIP2009普及组]分数线划定题目描述世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才,A市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的\(150\%\)划定,即如果计划录取\(m\)名志愿者,则面试分数......
  • [NOIP2009 普及组] 多项式输出
    题目描述一元\(n\)次多项式可用如下的表达式表示:\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,a_n\ne0\]其中,\(a_ix^i\)称为\(i\)次项,\(a_i\)称为\(i\)次项的系数。给出一个一元多项式各项的次数和系数,请按照如下规定的格式要求输出该多项式:多项式中自变量为\(......
  • P1067 [NOIP2009 普及组] 多项式输出
    #[NOIP2009普及组]多项式输出##题目描述一元$n$次多项式可用如下的表达式表示:$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,a_n\ne0$$其中,$a_ix^i$称为$i$次项,$a_i$称为$i$次项的系数。给出一个一元多项式各项的次数和系数,请按照如下规定的格式要求输出该多项......
  • P1074 [NOIP2009 提高组] 靶形数独
    题目传送门思路就是一个填数独的小游戏不会填数独的先去自己玩几把众所周知,数独每一行、每一列、每一个3*3宫格内的数字均含1~9,且不重复所以我们设三个数组r[10][10],c[10][10],block[10][10]分别记录行、列、3*3宫格内数字的使用情况重点:剪枝我们知道,数独的玩法是先从已知......
  • 2009年NOIP提高组真题-HanKson的趣味题(GCD&LCM优化)
    2009年NOIP提高组真题-HanKson的趣味题(GCD&LCM优化)本题的编码是用Python实现的,C++的思路也是相同的。希望本文能够帮助到你!题目:暴力法:直接根据题目的要求写:frommathimportgcddeflcm(a,b):returna*b//gcd(a,b)n=int(input())for_inrange(n):cnt=......
  • P1068 [NOIP2009 普及组] 分数线划定
    [NOIP2009普及组]分数线划定题目描述世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才,A市对所有报名的选手进行了笔试,笔试分数达到面试分数线的......
  • 【NOIP2009】【Vijos1752】潜伏者
    problemsolutioncodes#include<iostream>#include<string>#include<map>usingnamespacestd;map<char,char>ma,mm;stringans;intmain(){boolflag=t......
  • Hankson的趣味题
    Hankson的趣味题Hanks博士是BT(Bio-Tech,生物技术)领域的知名专家,他的儿子名叫Hankson。现在,刚刚放学回家的Hankson正在思考一个有趣的问题。今天在课堂上,老师讲解了......
  • P1073 [NOIP2009 提高组] 最优贸易 分层图
    //题意:给出有向图,有环(SCC),每个节点有一个商品值,小明想从1点走向n点,同时想要进行一次贸易,即从路线上某个点买入商品,又在某个节点卖出,询问最大收益是多少(如果收益为负数......