SquareFreeSet [2018 TCO Algorithm Round 2B Div1 Hard]

http://community.topcoder.com/stat?c=problem_statement&pm=14767

N要素の配列がある。
この配列の要素について「1つの要素の数を1つ増やすか1つ減らす操作」を任意の回数行う。
最小回数で、任意の2つの要素の積が平方数にならないようにせよ。

前提知識

• エラトステネスの篩的計算量
• 最小費用流

解説

公式解説の副読としてどうぞ
　
積を取って平方数であるかの判定のために、その数に含まれる平方数である因数は取り除いて考えていい。
よって、「f(x) := xの因数から平方数を取り除いたもの」と定義すると、f(x)=f(y)である場合に積が平方数となる。
　
まずは、このfを事前計算しよう。
以下のコードではpre配列が関数fにあたる。
2010以下の素数の二乗の数を使って、エラトステネスの篩の要領で、
もともとpre[i] = iだった中身から、平方数である因数を削っていく。
　
ある要素に対して、操作を何回か行って、別の数にするが、これはN*2回以上は行う必要が無い。
ある要素に対して、マッチングできる数がN*2個あるため、N個の要素のマッチング相手はO(N^2)個となる。
頂点数がO(N^2)なので、最小費用流できそうだ。
二部グラフの最小費用流をやろう。
以下のように頂点と辺を用意する。

• 始点→各要素：容量1, コスト0
• 各要素→f(変更後の数)：容量1, コストは変更後の数と各要素との差
• f(変更後の数)→終点：容量1, コスト0

これで始点から終点までNの流量を流して、得られた最小コストが答えとなる。

MinCostFlow<40101, ll> mcf;
int pre[1010101];
int memo[1010101];
struct SquareFreeSet {
    int findCost(vector<int> x) {
        int n = x.size();

        auto mp = makePrimes(2010);
        rep(i, 0, 1010101) pre[i] = i;
        fore(p, mp) {
            int pp = p * p;
            for (int i = pp; i < 1010101; i += pp) {
                while (pre[i] % pp == 0) pre[i] /= pp;
            }
        }

        vector<int> dic;
        rep(i, 0, n) rep(d, -(n * 2), n * 2) if (0 < x[i] + d) dic.push_back(pre[x[i] + d]);
        sort(all(dic));
        dic.erase(unique(all(dic)), dic.end());

        int m = dic.size();
        rep(i, 0, m) memo[dic[i]] = i;

        int st = n + m, gl = n + m + 1;

        rep(i, 0, n) mcf.add_edge(st, i, 1, 0);
        rep(i, 0, n) rep(d, -(n *2 ), n * 2) if (0 < x[i] + d) {
            int di = memo[pre[x[i] + d]];
            mcf.add_edge(i, n + di, 1, abs(d));
        }
        rep(i, 0, m) mcf.add_edge(n + i, gl, 1, 0);
        return mcf.mincost(st, gl, n);
    }
};