首先考虑连边的情况。
可以把 \(a_i\) 拆成 \(\gcd(a_i, m)\times \frac{a_i}{\gcd(a_i, m)}\)，因为 \(\gcd(\frac{a_i}{\gcd(a_i, m)}, m) = 1\)，所以与 \(a_i\) 有连边的 \(j\) 一定满足 \(j\bmod \gcd(a_i, m) = 0\)。
于是就可以把 \(c_{a_i}\) 放到 \(c_{\gcd(a_i, m)}\)，左部点就只剩下了 \(m\) 的因数了。
考虑左部点 \(i | m, j | m\)，满足 \(i | j\)，可以知道 \(j\) 所连向点 \(i\) 肯定也有连边。
具体就是令 \(R_x\) 为 \(x\) 与右部点有连边的点集合，对于 \(i | j\) 有 \(R_j\subset R_i\)。
于是一个想法就是对于右部点 \(y\)，与其有连边的左部点可能有很多个，但是把其挂到左部点 \(\gcd(y, m)\) 上，然后对于倍数去建边。
为什么是 \(\gcd(y, m)\)？因为对于左部点 \(x | m\)，若此时满足 \(x | \gcd(y, m)\)，就有 \(x | m\)；同时对于 \(x \nmid \gcd(y, m)\)，肯定 \(x\nmid y\)。
于是接下来就考虑如何算左部点 \(x\) 挂着的右部点个数。
官方题解用了个莫反，是不是太唐了点。
实际上这个值就是 \(\varphi(\frac{m}{x})\)，证明考虑选择了 \(y\in [1, \frac{m}{x}]\)。
那么 \(\gcd(m, xy) = x\gcd(y, \frac{m}{x})\)，所以当 \(\gcd(y, \frac{m}{x}) = 1\) 时满足 \(\gcd(m, xy) = x\)，这个 \(y\) 的个数显然就是 \(\varphi(\frac{m}{x})\) 了。
那么接下来就可以考虑网络流了。
因为此时右部点都是挂在左部点上的，所以不用建成一个二分图的形式。
具体的，对于左部点 \(x\)，连边 \((\operatorname{S}, x, c_x), (x, \operatorname{T}, \varphi(\frac{m}{x}))\)，相当于是把右部点也压缩进来了。
同时对于左部点 \(x | y\)，应该有连边 \((x, y, \operatorname{inf})\)，但这样边数太大了，考虑优化（但实际上这样就已经可以过了）。
一个想法是对于任意一个质数 \(p\)，\(x\) 的次数肯定都小于等于 \(y\) 的次数，所以若存在 \(p | y\)，连边 \((\frac{y}{p}, y, \operatorname{inf})\)。
然后跑网络流即可。
复杂度 \(\mathcal{O}(\sqrt{m} + \omega(m)d(m) + \operatorname{flow}(d(m), \omega(m)d(m)))\)。
其中 \(\omega(m)\) 表示 \(m\) 的质因子数量，\(d(m)\) 表示 \(m\) 的因子数量。
#include<bits/stdc++.h>
using ll = long long;
constexpr ll inf = 1e18;
const int maxN = 7e3 + 10, maxM = maxN + maxN + maxN * 12;
ll val[maxM * 2];
int to[maxM * 2], nxt[maxM * 2], fir[maxN], tot = 1;
int S, T;
inline void add(int x, int y, ll w, bool f = 1) {
to[++tot] = y, val[tot] = w, nxt[tot] = fir[x], fir[x] = tot;
if (f) add(y, x, 0, 0);
}
int hd[maxN], dep[maxN];
inline bool bfs() {
for (int i = 1; i <= T; i++)
hd[i] = fir[i], dep[i] = -1;
dep[S] = 0;
std::queue<int> Q; Q.push(S);
while (! Q.empty()) {
int u = Q.front(); Q.pop();
if (u == T) return true;
for (int i = hd[u]; i; i = nxt[i])
if (dep[to[i]] == -1 && val[i])
dep[to[i]] = dep[u] + 1, Q.push(to[i]);
}
return false;
}
inline ll dfs(int u, ll fl) {
if (u == T)
return fl;
ll ud = 0;
for (int &i = hd[u]; i; i = nxt[i])
if (dep[u] + 1 == dep[to[i]] && val[i]) {
ll k = dfs(to[i], std::min(fl - ud, val[i]));
if (! k) dep[to[i]] = -1;
ud += k, val[i] -= k, val[i ^ 1] += k;
if (ud == fl)
return fl;
}
return ud;
}
inline ll Dinic() {
ll ans = 0, f;
while (bfs())
while ((f = dfs(S, inf)) > 0)
ans += f;
return ans;
}
const int maxn = 7e3 + 10;
std::map<ll, int> id;
ll res[maxn], cnt[maxn];
std::vector<ll> pr;
inline void initpr(ll m) {
for (ll x = 2; x * x <= m; x++)
if (m % x == 0) {
pr.push_back(x);
while (m % x == 0) m /= x;
}
if (m > 1)
pr.push_back(m);
}
inline ll phi(ll x) {
ll v = x;
for (ll p : pr)
if (x % p == 0)
v /= p, v *= p - 1;
return v;
}
int main() {
int n; ll m; scanf("%d%lld", &n, &m);
for (ll i = 1; i * i <= m; i++)
if (m % i == 0)
id[i] = id[m / i] = 0;
initpr(m);
int N = 0;
for (auto &[x, c] : id)
c = ++N, res[N] = x;
for (ll a, c; n--; )
scanf("%lld%lld", &a, &c), cnt[id[std::__gcd(a, m)]] += c;
S = N + 1, T = N + 2;
for (int i = 1; i <= N; i++) {
add(S, i, cnt[i]);
add(i, T, phi(m / res[i]));
}
for (int i = 1; i <= N; i++)
for (ll p : pr)
if (res[i] % p == 0)
add(id[res[i] / p], i, inf);
printf("%lld\n", Dinic());
return 0;
}