Codeforces Round 900 (Div. 3) F

gcd(a, n) = 1并且d(a * n) == n

a、n互质说明a与n在>=2范围内没有公共因子，d(a * n) = d(a) * d(n)

d(a)可以是任意数，只要a的因子是n中没有的就行

所以问题转化为d(n)能否整除n，由于n可能很大不能直接算

这种时候可以将n分解为质因数的形式，看能否被d(n)除尽 

只要d(n)的质因数形式上的每一项的指数都小于等于n的质因数形式上的指数就说明可以除尽。

另外gcd(a, n)!=1时d(a * n)不一定等于d(a) * d(n)

所以应该只能枚举n的质因数来判断了

最坏情况是1000个2^p，最大在2^20次方左右，20存1000次是2e4，这1000次每次都要遍历完

最坏复杂度大约在1000 * 2e4 = 2e7左右，分解质因数复杂度为1000*sqrt(1e6)

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;
 
void solve()
{
	int n, q;
	cin >> n >> q;
	map<int, int>mp;
	
	ll num = 1;
	for(int i = 2; i * i <= n; i ++)
	{
		if(n % i == 0)
		{
			int c = 0;
			while(n % i == 0)
			{
				n /= i;
				c ++;
			}
			mp[i] += c;
			num *= c + 1;//n的因子个数 
		}
	}
	if(n > 1)
	{
		mp[n] ++;
		num *= 2;
	}
	
	map<int, int> mp_t = mp;
	ll num_t = num;
	
	while(q --)
	{
		int op;
		cin >> op;
		
		if(op == 1)
		{
			int x;
			cin >> x;
			
			for(int i = 2; i * i <= x; i ++)
			{
				if(x % i == 0)
				{
					int c = 0;
					while(x % i == 0)
					{
						x /= i;
						c ++;
					}
					num /= mp[i] + 1;
					mp[i] += c;
					num *= mp[i] + 1;
				}
			}
			if(x > 1)
			{
				num /= mp[x] + 1;
				mp[x] ++;
				num *= mp[x] + 1;
			}
			
			int t = num;
			for(auto item : mp)
			{
				int x = item.first, y = item.second;
				while(y > 0 && t % x == 0)
				{
					y --;
					t /= x;
				}
			}
			if(t == 1)cout << "YES" << endl;
			else cout << "NO" << endl;
		}
		else
		{
			mp = mp_t;
			num = num_t;
		}
	}
	cout << endl;
}
 
int main()
{
	IOS
	int _;
	cin >> _;
	while(_ --)
	{
		solve();
	}
	
	return 0;
}