Project Euler 518

题目

Prime triples and geometric sequences

Let \(S(n) = a+b+c\) over all triples \((a,b,c)\) such that:

• \(a, b\), and \(c\) are prime numbers.
• \(a < b < c < n\).
• \(a+1, b+1\), and \(c+1\) form a geometric sequence.

For example, \(S(100) = 1035\) with the following triples:

\(\begin{aligned} & (2, 5, 11), (2, 11, 47), (5, 11, 23), (5, 17, 53), (7, 11, 17), (7, 23, 71), (11, 23, 47), \\ & (17, 23, 31), (17, 41, 97), (31, 47, 71), (71, 83, 97) \end{aligned}\)

Find \(S(10^8)\).

解决方案

如果\(a+1,b+1,c+1\)是一个等比数列，那么不难观察出\((b+1)^2=(a+1)(c+1)\)。

那么，不难发现，如果\(a+1\)有一些质因子\(p\)的指数是奇数，那么为了确保\(b+1\)是一个平方数，\(c+1\)的质因子\(p\)的指数也必须是奇数。

假设函数\(f\)定义如下：\(f(n)=m\)意味着\(m\)是最小的因子使得\(\dfrac{n}{m}\)是平方数。

如果两个质数\(p,q\)满足\(f(p+1)=f(q+1)\)，那么这对\((p,q)\)才有可能产生一个答案。因此维护一些链表，这些链表用于存储\(f\)值相等情况下的\(n\)。

由于函数\(f\)值是无平方因子数，因此这些链表的数量比较多，长度也比较短，那么可以在每条链表上进行二重循环，枚举\(a+1,c+1\)的值。最终计算出\(b=\sqrt{(a+1)(c+1)}-1\)后，判断\(b\)是否为质数即可。

代码

#include <bits/stdc++.h>
#include "tools.h"
typedef long long ll;
using namespace std;
const int N=1e8;
const int M=N+1;
int v[M+4],pr[M/10+1000],f[M+4],head[M+4],pre[M+4];
int m=0;
int main(){
    for(int i=2;i<=N;i++){
        if(v[i]==0){
            f[i]=i;v[i]=i;pr[++m]=i;
        }
        for(int j=1;j<=m;j++){
            if(pr[j]>v[i]||pr[j]>N/i) break;
            v[i*pr[j]]=pr[j];
            f[i*pr[j]]=(f[i]%pr[j]==0?f[i]/pr[j]:f[i]*pr[j]);
        }
    }
    for(int i=1;i<=m&&pr[i]<=N;i++){
        int w=pr[i]+1;
        pre[w]=head[f[w]];
        head[f[w]]=w;
    }
    ll ans=0;
    for(int i=1;i<=N;i++)
        for(ll p=head[i];p;p=pre[p])
            for(ll q=pre[p];q;q=pre[q]){
                ll s= int_sqrt(1ll*p*q);
                if(v[s-1]==s-1) ans+=p+q+s-3;
            }
    printf("%lld\n",ans);

}