CF1878F Vasilije Loves Number Theory 题解

sunqihuan · 2025-10-21 23:24:46 · 题解

结论就是当 n 能被 d(n) 整除时为 Yes，其他题解都有详细讲解，不再赘述，这里主要讲一下实现。

这里的方法简单粗暴，对于 x，对它进行质因数分解，乘的 n 也分解并且和 x 的结果相加（开一个 map 即可）若直接计算 d(n) 是不可取的，所以我们可以采取逐步取模的策略，让结果不太大。

如何求 d(n) 大家应该都清楚就是用约数个数定理加上快速幂就可以快速求出了。

代码：

#include <bits/stdc++.h>

#define int long long 

using namespace std;

int ksm(int a, int b, int mod)
{
    int ans = 1;
    while (b)
    {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return (int)ans;
}

signed main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n, q;
        scanf("%lld%lld", &n, &q);
        map<int, int> now, org;
        int x = n;
        int lim = (int)floor(sqrt(x));
        for (int i = 2; i <= lim; i ++ )
        {
            while (x % i == 0)
            {
                now[i] ++ ;
                x /= i;
            }
        }
        if (x > 1) now[x] ++ ;
        org = now;
        while (q -- )
        {
            int op;
            scanf("%lld", &op);
            if (op == 2) now = org; 
            else
            {
                int t;
                scanf("%lld", &t);
                int tmp = t;
                int lim2 = (int)floor(sqrt(tmp));
                for (int i = 2; i <= lim2; i ++ )
                {
                    while (tmp % i == 0)
                    {
                        now[i] ++ ;
                        tmp /= i;
                    }
                }
                if (tmp > 1) now[tmp]++;
                int d = 1;
                map<int, int> :: iterator it = now.begin();
                while (it != now.end())
                {
                    int e = it->second;
                    d *= (e + 1);
                    it ++ ;
                }
                int res = 1;
                it = now.begin();
                while (it != now.end())
                {
                    int p = it->first, q = it->second;
                    int pw = ksm(p, q, d);
                    res = (res * pw) % d;
                    it ++ ;
                }
                if (res % d == 0) puts("YES");
                else puts("NO");
            }
        }
        puts("");
    }
    return 0;
}