CF1878F Vasilije Loves Number Theory 题解

#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;
}