F. Vasilije Loves Number Theory

Problem - F - Codeforces

思路：分析一下题意，对于第一种操作来说，每次乘以x，那么n=n*x，然后问是否存在一个a使得gcd(n,a)=1并且n*a的约数个数等于n，有最大公约数等于1我们能够知道其实这两个数是互质的，所以d(n)*d(a)=d(n*a)，那么就是要d(a)=n/d(n)，所以n%d(n)一定要等于零，同时又因为当取模等于零时我们发现一定可以构造除一种方案，我们先选择一个与n互质的数x，然后让a=x^t，此时a共有(t+1)个约数，所以我们只需要让(t+1)=n/d(n)就能够构造出来，所以现在的问题变成了，我们能够判断n%d(n)等于0，我们知道一个因数个数的公式，就是所有质因数的个数加一的累乘，那么我们只需要维护n的所有质因数的个数即可，同时n并不能够直接乘以x，因为可能会乘的很大，所以我们在求出来d(n)之后，可以看看n与所有的x能否把d(n)消完，如果能消则代表可以

// Problem: F. Vasilije Loves Number Theory
// Contest: Codeforces - Codeforces Round 900 (Div. 3)
// URL: https://codeforces.com/contest/1878/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
 
#include
#include
#include
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
const double eps=1e-7;
const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}
 
int T,hackT;
ll n,m,k;
int pr[N],ttcnt;
bool st[N];
int cnt[N];
map<int,int> tcnt;
 
void init() {
	for(int i=2;i<=1000;i++) {
		if(!st[i]) pr[ttcnt++]=i;
		for(int j=0;pr[j]<=1000/i;j++) {
			st[pr[j]*i]=true;
			if(i%pr[j]==0) break;
		}
	}
}
 
void t_init(int x) {
	tcnt.clear();
	for(int i=0;i0;
	for(int j=0;j
		if(pr[j]>x) break;
		while(x%pr[j]==0) {
			cnt[pr[j]]++;
			x/=pr[j];
		}
	}
	if(x!=1) tcnt[x]++;
}
 
int get() {
	int res=1;
	for(int i=0;i1);
	for(auto &it:tcnt) res=res*(it.se+1);
	return res;
}
 
void change(int x,int &d) {
	int s=gcd(x,d);
	d/=s;
}
 
bool check(vector<int> &temp,int d) {
	change(n,d);
	for(int i=0;isize();i++) change(temp[i],d);
	
	if(d==1) return true;
	else return false;
}
 
void solve() {
	n=read();
	int q=read();
	
	t_init(n);
	vector<int> temp;
	while(q--) {
		int op=read();
		
		if(op==1) {
			int x=read();
			temp.push_back(x);
			for(int j=0;j
				if(pr[j]>x) break;
				while(x%pr[j]==0) {
					cnt[pr[j]]++;
					x/=pr[j];
				}
			}
			if(x!=1) tcnt[x]++;
			
			if(check(temp,get())) printf("YES\n");
			else printf("NO\n");
		}else if(op==2) {
			t_init(n);
			temp.clear();
		}
	}
}   
 
int main() {
    init();
    // stin();
	// ios::sync_with_stdio(false); 
 
    scanf("%d",&T);
    // T=1; 
    while(T--) hackT++,solve();
    
    return 0;       
}