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<bits/stdc++.h>
#include<sstream>
#include<cassert>
#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;i<ttcnt;i++) cnt[pr[i]]=0;for(int j=0;j<ttcnt;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;i<ttcnt;i++) res=res*(cnt[pr[i]]+1);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;i<temp.size();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<ttcnt;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;       
}