Project Euler 273

题目

Sum of Squares

Consider equations of the form: $a^2 + b^2 = N$, $0 \le a \le b$, $a, b$ and $N$ integer.

For $N=65$ there are two solutions:$a=1, b=8$ and $a=4, b=7$.

We call $S(N)$ the sum of the values of $a$ of all solutions of $a^2 + b^2 = N$, $0 \le a \le b$, $a, b$ and $N$ integer.

Thus $S(65) = 1 + 4 = 5$.

Find $\sum S(N)$, for all squarefree $N$ only divisible by primes of the form $4k+1$ with $4k+1 < 150$.

婆罗摩笈多——斐波那契恒等式

婆罗摩笈多——斐波那契恒等式说明，如果两个整数分别能表示成两个平方数之和，那么这两个整数的积也能表示成两个平方数之和：

$$(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2=(ac+bd)^2+(ad-bc)^2$$

解决方案

页面1，页面2说明了一个奇质数当且仅当它模$4$余$1$，才能表示成两个不同平方数之和，并且表示方式是唯一的。

我们先求出$M=150$以内的所有模$4$余$1$的唯一平方数之和的表示$p_i=a_i^2+b_i^2$，然后根据婆罗摩笈多——斐波那契恒等式，将每一对表示方式进行不同的组合即可。

代码

# include <bits/stdc++.h>
# include "tools.h"
using namespace std;
typedef long long ll;
const int N=150;
vector<int>pr,u,v;
ll dfs(int f,ll a,ll b){
    if(f==u.size()) return min(abs(a),abs(b));
    return dfs(f+1,a,b)+dfs(f+1,a*u[f]-b*v[f],a*v[f]+b*u[f])+dfs(f+1,a*u[f]+b*v[f],a*v[f]-b*u[f]);
}
int main() {
    for(int p=1;p<N;p+=4)
        if(is_prime(p)){
            pr.push_back(p);
            for(int a=1;a*a<=p;a++){
                int b=int_square(p-a*a);
                if(a*a+b*b==p){
                    u.push_back(a);
                    v.push_back(b);
                    break;
                }
            }
        }
    ll ans=0;
    for(int i=0;i<u.size();i++)
        ans+=dfs(i+1,u[i],v[i]);
    printf("%lld\n", ans);
}