给定整数$1 < a_1 < a_2 < \ldots < a_n$，考虑其非负线性组合$q_1a_1+q_2a_2+\ldots+q_na_n=b$，其中$q_k\ge 0$均为整数。

不难看出，并不是所有的整数b值都能取到。例如，若$a_1=5, a_2=7$，则b取不到1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18, 23。

记$f(a_1,\ldots,a_n)$为给定的$a_1,a_2,\ldots,a_n$的非负线性组合所不能取得的最大b值，例如$f(5,7) = 23$。

类似地，可以验证$f(6, 10, 15)=29$以及$f(14, 22, 77) = 195$。

对于所有满足$p < q < r < 5000$的素数p,q,r，求$\sum\limits_{p,q,r}f(pq,pr,qr)$。

本题难度:

解答

根据此论文中的定理一，若$\gcd(a_1,\ldots,a_n)=1$，则 $$f(a_1,\ldots,a_n)=(n-1-\sum_{i=1}^n\frac{1}{a_i})P,$$ 其中$P=\prod\limits_{i=1}^n$，因此， $$f(pq,qr,pr)=2pqr-pr-qr-pq.$$ 不超过5000的素数只有669个，直接枚举全部组合计算即得结果$1228215747273908452$。

import itertools

target=5000
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

print sum(2*p*q*r-p*q-p*r-q*r for p,q,r in itertools.combinations([k for k in range(2,target) if d[k]==0],3))