#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; int N = n*n; vector<int> diff(N, 0); vector<int> squares(n+1); for(int i=0; i<=n; i++) squares[i] = i*i; for(int d=n; d>0; d--) for(int c=d-1; c>0; c--) diff[squares[d] - squares[c]]++; int count = 0; for(int a=1; a<n; a++) { for(int b=a; b<n; b++) { int sum = squares[a] + squares[b]; if(sum > N) continue; count += diff[sum]; } } cout << count << "\n"; return 0; } /* a^2 + b^2 + c^2 = d^2 a^2 + b^2 = d^2 - c^2 for alg let's assume: - d > a,b,c - a <= b we want to count solutions [p, q, q] (p<q) twice, when {a=p,b=q,c=q} and {a=q,b=q,c=p} for (p<q<r) we get {a=p,b=q,c=r}, {a=p,b=r,c=q} and {a=q,b=r,c=p} goal: memorize d^2-c^2 and check for a^2+b^2 */
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; int N = n*n; vector<int> diff(N, 0); vector<int> squares(n+1); for(int i=0; i<=n; i++) squares[i] = i*i; for(int d=n; d>0; d--) for(int c=d-1; c>0; c--) diff[squares[d] - squares[c]]++; int count = 0; for(int a=1; a<n; a++) { for(int b=a; b<n; b++) { int sum = squares[a] + squares[b]; if(sum > N) continue; count += diff[sum]; } } cout << count << "\n"; return 0; } /* a^2 + b^2 + c^2 = d^2 a^2 + b^2 = d^2 - c^2 for alg let's assume: - d > a,b,c - a <= b we want to count solutions [p, q, q] (p<q) twice, when {a=p,b=q,c=q} and {a=q,b=q,c=p} for (p<q<r) we get {a=p,b=q,c=r}, {a=p,b=r,c=q} and {a=q,b=r,c=p} goal: memorize d^2-c^2 and check for a^2+b^2 */ |