题目描述

难度分:$1900$

定义$d(N)$为$N$的因子个数。输入$T(\leq 100)$表示$T$组数据。所有数据的$q$之和$\leq 1000$。

每组数据输入$n_0(1 \leq n_0 \leq 10^6)$，$q(1 \leq q \leq 1000)$以及$q$询问。

初始化$n=n_0$。然后输入$q$个询问，格式如下：

1. 1 x$(1 \leq x \leq 10^6)$：把$n$更新为$n \times x$，同时询问：是否存在一个正整数 $a$，满足$gcd(n,a)=1$且$d(n \times a)=n$？输出YES或NO。
2. 2：把$n$更新为$n_0$。

保证任何时刻$d(n) \leq 10^9$。

输入样例$1$

7
1 5
1 1
1 2
2
1 8
1 9
20 4
1 3
2
1 7
1 12
16 10
1 6
1 6
1 10
1 9
1 1
1 9
1 7
1 3
1 2
1 10
9 1
1 3
8 1
1 2
8 3
1 5
1 8
1 10
11 5
1 8
1 2
1 1
1 3
1 1

输出样例$1$

YES
YES
YES
YES

YES
NO
YES

YES
NO
YES
YES
YES
NO
YES
NO
YES
YES

NO

NO

YES
NO
NO

YES
NO
NO
NO
NO

算法

质因数分解

这个题出思路还是挺快的，由于$n \leq 10^6$，$x \leq 10^6$，在极限情况下乘不了几次就会爆$long$ $long$，因此需要对这些数都分解质因数。

对于输入的$n_0$，先分解质因数存入到哈希表$counter$中，并保存一个副本哈希表$cache$。然后在线处理每一条询问：

1. 对于第一类询问，将$x$也分解质因数，然后各个因子的个数都累加到$counter$中，这样$counter$就变成了$n \times x$的质因数分解结果。首先注意到找到满足$gcd(a,n)=1$的$a$简直易如反掌，直接用$counter$中不存在的质因子组成$a$就可以了，这样一定可以保证$n$和$a$是互质的。再考虑$d(n \times a)=n$，对于一个整数$num$，它可以进行唯一分解$num=p_1^{\alpha_1}p_2^{\alpha_1}…p_k^{\alpha_k}$，$num$的约数个数应该是$(\alpha_1+1)(\alpha_2+1)…(\alpha_k+1)$。而$d(n)$在本题中任何时候都不会超过$10^9$，说明不会爆$int$，先遍历$counter$计算出$n$的约数个数$res$，再对$res$进行质因数分解，将结果存到哈希表$temp$中。要想$d(n \times a)=n$成立，只需要$res|n$成立即可，即$temp$是$counter$的子集。
2. 对于第二类询问，将$n$又还原成$n_0$，只需要将$cache$表再赋值给$counter$即可。

复杂度分析

时间复杂度

由于题面存在$\Sigma$的约束，这里只分析每个$case$的时间复杂度。分解质因数我用的是$Pollard$ $Rho$算法，时间复杂度大概是$\sqrt[4]{n}$这个级别，先对$n$分解质因数，时间复杂度为$O(\sqrt[4]{n})$。

然后处理每个询问，主要考虑第一类询问的时间复杂度，先对$x$分解质因数，时间复杂度为$\sqrt[4]{x}$，接下来合并$n$和$x$的质因子个数，在本题的数据范围下，质因子个数最多也就几百个，合并完成后计算$n$的约数个数，再判断$res$是否能被$n$整除，时间复杂度都是质因子个数的级别。

综上，整个算法的时间复杂度为$O(\sqrt[4]{n}+q(\sqrt[4]{x}+A))$，其中$A$为质因子个数的上限，$x$和$n$是一个级别的。

空间复杂度

空间消耗的瓶颈主要在于质因数分解的结果存储，因此额外空间复杂度可以近似看做$O(A)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int t, n, q;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// Miller-Rabin算法判断质数
LL fast_power(__int128 a, LL k, LL p) {
    LL res = 1 % p;
    while(k) {
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

bool miller_rabin(LL n) {
    if(n == 2) return true;
    if(n <= 1 || n % 2 == 0) return false;
    LL base[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    LL u = n - 1, k = 0;
    while(!(u&1)) u >>= 1, k++;
    for(auto&x: base) {
        if(x % n == 0) continue;
        LL v = fast_power(x, u, n);
        if(v == 1 || v == n - 1) continue;
        for(int j = 1; j <= k; j++) {
            LL last = v;
            v = (__int128)v * v % n;
            if(v == 1) {
                if(last != n - 1) return false;
                break;
            }
        }
        if(v != 1) return false;
    }
    return true;
}

// Pollard-Rho分解质因数
LL Pollard_Rho(LL n) {
    static mt19937_64 sj(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<LL> u0(1, n - 1);
    LL c = u0(sj);
    auto f = [&](LL x) {
        return ((__int128)x * x + c) % n;
    };
    LL x = f(0), y = f(x);
    while(x != y) {
        LL d = __gcd(abs(x - y), n);
        if(d != 1) return d;
        x = f(x), y = f(f(y));
    }
    return n;
}

void get_factor(LL n, unordered_map<LL, int, custom_hash>& counter) {
    if(n == 1) return;
    if(n == 4) {
        counter[2] += 2;
        return;
    }
    if(miller_rabin(n)) {
        counter[n] += 1;
        return;
    }
    LL x = n;
    while(x == n) x = Pollard_Rho(n);
    get_factor(x, counter);
    get_factor(n/x, counter);
}

bool check(unordered_map<LL, int, custom_hash>& mp1, unordered_map<LL, int, custom_hash>& mp2) {
    for(auto&[k, v]: mp2) {
        if(!mp1.count(k) || mp1[k] < v) {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &q);
        unordered_map<LL, int, custom_hash> counter, cache;
        get_factor(n, counter);
        for(auto&[num, cnt]: counter) {
            cache[num] = cnt;
        }
        for(int i = 1; i <= q; i++) {
            int k, x;
            scanf("%d", &k);
            if(k == 1) {
                scanf("%d", &x);
                unordered_map<LL, int, custom_hash> temp1;
                get_factor(x, temp1);
                for(auto&[num, cnt]: temp1) {
                    counter[num] += cnt;
                }
                int res = 1;     // n的因子个数
                for(auto&[factor, cnt]: counter) {
                    res *= cnt + 1;
                }
                unordered_map<LL, int, custom_hash> temp2;
                get_factor(res, temp2);
                if(check(counter, temp2)) {
                    puts("YES");
                }else {
                    puts("NO");
                }
            }else {
                counter = cache;
            }
        }
        puts("");
    }
    return 0;
}