自动搬运

查看原文

来自洛谷，原作者为

	rizynvu w

搬运于2025-08-24 23:02:31，当前版本为作者最后更新于2024-08-24 08:54:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的博客。

首先考虑连边的情况。
可以把 $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;
}