简单网站建设协议书,在线代理网页免费,找一家秦皇岛市做网站的公司,seo优化知识Problem - F - Codeforces 思路#xff1a;分析一下题意#xff0c;对于第一种操作来说#xff0c;每次乘以x#xff0c;那么nn*x#xff0c;然后问是否存在一个a使得gcd(n,a)1并且n*a的约数个数等于n#xff0c;有最大公约数等于1我们能够知道其实这两个数是互质的…Problem - F - Codeforces 思路分析一下题意对于第一种操作来说每次乘以x那么nn*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然后让ax^t此时a共有(t1)个约数所以我们只需要让(t1)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#includebits/stdc.h
#includesstream
#includecassert
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pairint,int PII;
const double eps1e-7;
const int N5e57 ,M5e57, INF0x3f3f3f3f,mod1e97,mod1998244353;
const long long int llINF0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x0,f1;char cgetchar();while(c0||c9) {if(c-) f-1;cgetchar();}
while(c0c9) {x(ll)x*10c-0;cgetchar();} 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 ab;}
templatetypename T T gcd(T a,T b) {return b0?a:gcd(b,a%b);}
templatetypename 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];
mapint,int tcnt;void init() {for(int i2;i1000;i) {if(!st[i]) pr[ttcnt]i;for(int j0;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 i0;ittcnt;i) cnt[pr[i]]0;for(int j0;jttcnt;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 res1;for(int i0;ittcnt;i) resres*(cnt[pr[i]]1);for(auto it:tcnt) resres*(it.se1);return res;
}void change(int x,int d) {int sgcd(x,d);d/s;
}bool check(vectorint temp,int d) {change(n,d);for(int i0;itemp.size();i) change(temp[i],d);if(d1) return true;else return false;
}void solve() {nread();int qread();t_init(n);vectorint temp;while(q--) {int opread();if(op1) {int xread();temp.push_back(x);for(int j0;jttcnt;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(op2) {t_init(n);temp.clear();}}
} int main() {init();// stin();// ios::sync_with_stdio(false); scanf(%d,T);// T1; while(T--) hackT,solve();return 0;
}
