Project Euler 135

题目

Same differences

Given the positive integers, \(x, y\), and \(z\), are consecutive terms of an arithmetic progression, the least value of the positive integer, \(n\), for which the equation, \(x^2 − y^2 − z^2 = n\), has exactly two solutions is \(n = 27\):

\[34^2 − 27^2 − 20^2 = 12^2 − 9^2 − 6^2 = 27\]

It turns out that \(n = 1155\) is the least value which has exactly ten solutions.

How many values of \(n\) less than one million have exactly ten distinct solutions?

解决方案

\(x,y,z\)是一个等差数列，并且由于\(n>0\)，因此只有当\(x>y>z\)时，才会有\(x^2-y^2-z^2>0\)。

因此设公差为\(d\)，那么有\((z+2d)^2-(z+d)^2-z^2=n\)。

将方程左边化简，并分解因式，有\((3d-z)(d+z)=n\)。

故在枚举方程的解过程中，先枚举\(z\)的值，再枚举\(d\)的值，注意\(d\)的值要从\(\left\lfloor\dfrac{z}{3}\right\rfloor+1\)开始枚起来，这样才能保证一开始的\(n\)的正数。

代码

# include <bits/stdc++.h>
using namespace std;
const int N=1e6,Q=10;
int c[N+4];
int main(){
    for(int z=1;z<=N;z++){
        for(int d=z/3+1;;d++){
            int w=(3*d-z)*(d+z);
            if(w>=N) break;
            c[w]+=1;
        }
    }
    int ans=0;
    for(int i=1;i<=N;i++)
        if(c[i]==Q) ++ans;
    printf("%d\n",ans);
}