Luogu P10918 小分图最大匹配

· · 题解

我的博客。

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