F. Vasilije Loves Number Theory
前提知识：d(n)表示数字n的正约数个数，gcd(a,b)表示a,b两者的最大公约数
要点：问是否存在a,使得d(a * n)=n,gcd(n,a)=1，意思是n与a互质，
则可得，d(a * n)=d(a)*d(n)=n
则问题转化成n%d(n)==0？
尽管d(n)<=1e9，但n可能很大，所以可以利用质因子来求
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
void solve() {
LL n, q,x;
cin >> n >> q;
x = n;
map<LL, LL> now, old;
for (LL i = 2; i * i <= x; i++) {//计算正约数的几次幂
while (x % i == 0) {
x /= i;
now[i]++;
}
}
if (x > 1) {
now[x]++;
}
old = now;
while (q--) {
int op;
cin >> op;
if (op == 1) {
LL s;
cin >> s;
//同上
for (int i = 2; i * i <= s; i++) {
while (s % i == 0) {
s /= i;
now[i]++;
}
}
if (s > 1) now[s]++;
//计算s*n的正约数数量
LL ans = 1;
for (auto v : now) {
ans *= (v.second + 1);
}
//快速幂
auto f = [](LL a, LL b, LL mod) {
LL res = 1;
while (b) {
if (b & 1) res = (res * a) % mod;
a = a * a % mod;
b >>= 1;
}
return res;
};
//计算s*n的值
LL mod = 1;
for (auto v : now) {
mod = (mod * f(v.first, v.second, ans)) % ans;
}
//输出
if (mod %ans == 0) {
cout << "YES\n";
}
else cout << "NO\n";
}else {//还原
now = old;
}
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}