Project Euler 355

题目

Maximal coprime subset

Define \(Co(n)\) to be the maximal possible sum of a set of mutually co-prime elements from \(\{1, 2, \dots, n\}\).

For example \(Co(10)\) is \(30\) and hits that maximum on the subset \(\{1, 5, 7, 8, 9\}\).

You are given that \(Co(30) = 193\) and \(Co(100) = 1356\).

Find \(Co(200000)\).

解决方案

令\(N=200000\)，令函数\(f(n,p)\)表示求\(p\)最大的质数幂\(p^k\le n\)。

本题基于这个假设完成：被选上集合的数\(n\)，必定是以下两类数之一：

• \(f(n,p)\).对于\(N\)以内的任何一个质数\(p\)。
• \(f\left(\left\lfloor\dfrac{n}{q}\right\rfloor,p\right)\cdot q\)，其中\(p\)是一个质数，\(q\)是一个大于\(\lfloor\sqrt{N}\rfloor\)的质数。

如果质数\(p,q\)构造出了候选答案的第二类数，那么其它第二类数必定不能含有\(p,q\)这两个质因子，因此我们可以将其转化成最小费用最大流问题来解决。一开始我们先假设候选答案中只有第一类数，其总和为\(s\)，往后再逐渐添加第二类数。

假设小于等于\(\lfloor\sqrt{N}\rfloor\)的质数为集合\(P\)，其余质数为集合\(Q\)。对于\(p\in P,q \in Q\)，如果\(f\left(\left\lfloor\dfrac{n}{q}\right\rfloor,p\right)\cdot p>f(n,p)+q\)，那么从节点\(p\)到节点\(q\)连一条容量为\(1\)，费用为\(-\left(f\left(\left\lfloor\dfrac{n}{q}\right\rfloor,p\right)\cdot p-f(n,p)-q\right)\)的边。那么，将源点连向\(P\)中的每个节点，将\(Q\)中的每个节点连向汇点，这些边的容量都为\(1\)，费用都为\(0\)。

最终使用networkx库中的max_flow_min_cost方法完成计算。将答案添加到\(s\)中，成为最终答案。需要注意的是，我们求的费用是最大值，因此整张图的费用权值都是负数。

代码

from tools import get_prime
import networkx as nx

N = 200000


def cal(n, p):
    m = 1
    while m * p <= n:
        m *= p
    return m


pr = get_prime(N)
g = nx.DiGraph()
ans = 1
st, ed = [], []
s, t = -1, -2
for p in pr:
    ans += cal(N, p)
    if p ** 2 <= N:
        g.add_edge(s, p, capacity=1, weight=0)
        st.append(p)
    elif p + p <= N:
        g.add_edge(p, t, capacity=1, weight=0)
        ed.append(p)
for p in st:
    for q in ed:
        if p * q > N:
            break
        k = cal(N // q, p) * q
        if cal(N, p) + q < k:
            g.add_edge(p, q, capacity=1, weight=-(k - cal(N, p) - q))

ans += -nx.cost_of_flow(g, nx.max_flow_min_cost(g, s, t))
print(ans)