有意思的。
对 \(k\) 分解质因数，题目实际上是想让我们解一个 \(\sum\limits_{i = 1}^m a_i x_i = n\) 的方程。
考虑 \(m = 1\) 特判，\(m = 2\) exgcd。\(m = 3\) 时发现 \(\min\limits_{i = 1}^m a_i \le k^{\frac{1}{3}} \le 10^5\)，所以可以跑同余最短路。设 \(f_i\) 为能组成的 \(\bmod a_1 = i\) 的最小数。那么就直接判 \(f_{n \bmod a_i} \le n\) 即可。
同余最短路还在写最短路？感觉不如转圈！
code
// Problem: F. Oppa Funcan Style Remastered
// Contest: Codeforces - Codeforces Round 485 (Div. 1)
// URL: https://codeforces.com/problemset/problem/986/F
// Memory Limit: 256 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 10050;
const int N = 32000000;
ll n, ans[maxn], m, f[maxn * 10];
int pr[N / 10], tot;
bool vis[N + 5];
struct node {
ll n, k, i;
} qq[maxn];
inline void init() {
for (int i = 2; i <= N; ++i) {
if (!vis[i]) {
pr[++tot] = i;
}
for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {
vis[i * pr[j]] = 1;
if (i % pr[j] == 0) {
break;
}
}
}
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &qq[i].n, &qq[i].k);
qq[i].i = i;
}
sort(qq + 1, qq + n + 1, [&](const node &a, const node &b) {
return a.k < b.k;
});
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && qq[j + 1].k == qq[i].k) {
++j;
}
m = qq[i].k;
if (m == 1) {
for (int k = i; k <= j; ++k) {
ans[qq[k].i] = 0;
}
continue;
}
vector<ll> P;
for (int k = 1; k <= tot && 1LL * pr[k] * pr[k] <= m; ++k) {
if (m % pr[k] == 0) {
P.pb(pr[k]);
while (m % pr[k] == 0) {
m /= pr[k];
}
}
}
if (m > 1) {
P.pb(m);
}
if ((int)P.size() == 1) {
for (int k = i; k <= j; ++k) {
ans[qq[k].i] = (qq[k].n % P[0] == 0);
}
continue;
}
if ((int)P.size() == 2) {
ll p, q;
ll d = exgcd(P[0], P[1], p, q);
for (int k = i; k <= j; ++k) {
lll x = p, y = q;
if (qq[k].n % d) {
ans[qq[k].i] = 0;
continue;
}
x *= (qq[k].n / d);
y *= (qq[k].n / d);
lll pp = P[1] / d, qq = P[0] / d;
if (x < 0) {
lll t = (-x + pp - 1) / pp;
x += t * pp;
y -= t * qq;
}
if (x > 0) {
lll t = x / pp;
x -= t * pp;
y += t * qq;
}
ans[::qq[k].i] = (x >= 0 && y >= 0);
}
continue;
}
for (int i = 1; i <= P[0]; ++i) {
f[i] = 8e18;
}
f[0] = 0;
ll t = P[0];
for (int i = 1; i < (int)P.size(); ++i) {
for (ll j = 0, lim = __gcd(P[i], t); j < lim; ++j) {
for (ll k = j, c = 0; c < 2; c += (k == j)) {
ll p = (k + P[i]) % t;
f[p] = min(f[p], f[k] + P[i]);
k = p;
}
}
}
for (int k = i; k <= j; ++k) {
ans[qq[k].i] = (f[qq[k].n % t] <= qq[k].n);
}
}
for (int i = 1; i <= n; ++i) {
puts(ans[i] ? "YES" : "NO");
}
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}