1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
| # include <cmath> # include <stdio.h> # include <cassert> # include <algorithm> typedef long long LL; const int maxn = 31623, maxm = 17, maxp = 61, maxt = 100001, maxv2 = (int)1e9; const LL maxv = (LL)1e18; int tot, pr[maxn], d[maxn], sz[maxm]; LL pp[maxm][maxn]; bool isprime(int x) { if(x < 2) return 0; if(x < maxn) return d[x] == x; for(int i = 0; i < tot && pr[i] * pr[i] <= x; ++i) if(x % pr[i] == 0) return 0; return 1; } int main() { for(int i = 2; i < maxn; ++i) { if(!d[i]) pr[tot++] = d[i] = i; for(int j = 0, k; (k = i * pr[j]) < maxn; ++j) { d[k] = pr[j]; if(d[i] == pr[j])break; } }
for(int i = 2; i < maxm; ++i) for(int j = 0; j < tot; ++j) { int rem = pr[i] - 1; LL val = 1, lim = maxv / pr[j]; for( ; rem && val <= lim; --rem, val *= pr[j]); if(rem) break; pp[i][sz[i]++] = val; }
int t; LL n, p; assert(scanf("%d", &t) == 1 && 1 <= t && t < maxt); while(t--) { assert(scanf("%lld%lld", &n, &p) == 2 && 1 <= n && n <= maxv && (p & 1) && p <= maxv2 && isprime(p)); if(p >= maxp || d[p] != p) { puts("NO"); continue; } if(p == 3) { LL val = (LL)sqrt(n); for( ; val * val > n; --val); for( ; (val + 1) * (val + 1) <= n; ++val); puts(val * val == n && isprime(val) ? "YES" : "NO"); continue; } for(int i = 2; i < maxm; ++i) if(pr[i] == p) { puts(*std::lower_bound(pp[i], pp[i] + sz[i], n) == n ? "YES" : "NO"); break; } } return 0; }
|