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

/*
    "爆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;
}