Project Euler 127

题目

abc-hits

The radical of $n$, $\text{rad}(n)$, is the product of the distinct prime factors of $n$. For example, $504 = 2^3 × 3^2 × 7$, so $\text{rad}(504) = 2 × 3 × 7 = 42$.

We shall define the triplet of positive integers $(a, b, c)$ to be an $abc$-hit if:

1. $\gcd(a, b) = \gcd(a, c) = \gcd(b, c) = 1$
2. $a < b$
3. $a + b = c$
4. $\text{rad}(abc) < c $;

For example, $(5, 27, 32)$ is an abc-hit, because:

1. $\gcd(5, 27) = \gcd(5, 32) = \gcd(27, 32) = 1$
2. $5 < 27$
3. $5 + 27 = 32$
4. $\text{rad}(4320) = 30 < 32$

It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for $c < 1000$, with $\sum c = 12523$.

Find $\sum c$ for $c < 120000$.

解决方案

按照第124题的方式计算出所有$\text{rad}$的值。

由于第三条$a+b=c$，因此判断$a,b,c$的两两互质性，只需要判断其中的某一对。因为由求其中一对的最大公因数时，可以通过辗转相除法，转成另外两对。

根据$\text{rad}(n)$的定义，是由$n$的不同的质因数相乘得出的值。那么由于$a,b,c$两两互质，它们之间没有相同的质因数，因此$\text{rad}(abc)=\text{rad}(a)\cdot \text{rad}(b)\cdot \text{rad}(c)$。

这给我们提供了一个思路，首先将$1\sim N$中的所有值按照函数值$\text{rad}$从小到大排序。先从小到大枚举$c$的值，然后再按照$\text{rad}$的大小从小到大枚举$a$的值。当$\text{rad}(a)\cdot \text{rad}(c)\ge c$时，就可以停止枚举$a$了。剩下的就是判断其它答案是否符合条件。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=120000-1;
int rad[N+4],rk[N+4];
int main(){
    for(int i=1;i<=N;i++)
        rk[i]=i,rad[i]=1;
    for(int i=2;i<=N;i++){
        if(rad[i]==1){
            for(int j=i;j<=N;j+=i)
                rad[j]*=i;
        }
    }
    sort(rk+1,rk+N+1,[&](int &x,int &y){
         return rad[x]<rad[y]||rad[x]==rad[y]&&x<y;
         });
    ll ans=0;
    for(int c=1;c<=N;c++){
        for(int i=1;i<=N;i++){
            int a=rk[i];
            if(rad[a]*rad[c]>=c)
                break;
            if(__gcd(a,c)!=1) continue;
            int b=c-a;
            if(a<b && 1ll*rad[a]*rad[b]*rad[c]<c)
                ans+=c;
        }
    }
    printf("%lld\n",ans);
}