Vasilije Loves Number Theory

Created by LXC on Thu Jan 18 12:55:58 2024

https://codeforces.com/problemset/problem/1878/F

ranting: 1900

tag: brute force, math, number theory

problem

令 $d(x)$ 表示 $x$ 的正因子数量，给定 $n,q$。现有两种操作：

1. 给定 $x$，令 $n\gets n\cdot x$。同时询问是否存在一个正整数 $a$ 满足 $\gcd(a,n)=1$ 且 $d(n\cdot a)=n$。

2. 将 $n$ 还原为最初的值。

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

translated by @StayAlone

solution

我们知道一个正整数n有$\sqrt n$数量级的因子。求n的因子数可以在$O(\sqrt n)$时间内完成。

$d(n)\leq 10^9$说明n的至少为$10^18$，对于每次更新后的n，应该可以用long long型变量存下，但是不能直接求其因子数。

我们采用最常用的方法，质因数分解。假设$n = p_1^{a_1}p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，$p_i$为质数，$a_i$为质数出现的次数。n的因子个数为$d(n) = (a_1+1)(a_2+1)\cdots (a_k+1)$
n每乘以一个x，就将x质因数分解，更新n的质因子集合。

要求存在一个数k，$gcd(k,n) = 1, d(nk)=n$，由于$d(nk) = d(n)d(k)$，如果$d(n)$是n的因子那么我们总能找到这样的k。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n, q;
    cin >> n >> q;
    map<int,int> mp;
    auto sp = [&](int x) {
        for (int i=2; i*i<=x; i++) {
            while (x%i == 0) {
                x /= i;
                mp[i]++;
            }
        }
        if (x != 1) mp[x]++;
    };
    auto d = [&]() {
        int rt = 1;
        for (auto [i,j]:mp) {
            rt *= j+1;
        }
        return rt;
    };
    auto check = [&](int x) {
        for (int i=2; i*i<=x; i++) {
            if (x%i) continue;
            int c = 0;
            while (x%i == 0) {
                x /= i;
                c++;
            }
            if (!mp.count(i) || mp[i] < c) return false;
        }
        if (x != 1) {
            if (!mp.count(x)) return false;
        }
        return true;
    };
    sp(n);
    for (int i=0; i<q; i++) {
        int k, x;
        cin >> k;
        if (k == 1) {
            cin >> x;
            sp(x);
            if (check(d())) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        } else {
            mp.clear();
            sp(n);
        }
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}