#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define imie(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const int mod=1e9+7; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int S = n * n - 1; vector<ll> cnt(S + 1, 0); for(int a = 1; a <= n; a++){ ll a2 = a * a; for(int b = a; b <= n; b++){ ll s = a2 + b * b; if(s > S) break; cnt[s]++; } } ll ans = 0; for(int h = 1; h <= n; h++){ ll h2 = h * h; for(int d = h + 1; d <= n; d++){ ll d2 = d * d; ll s = d2 - h2; if(s > S) continue; ans += cnt[s]; } } cout << ans << "\n"; return 0; }
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> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define imie(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const int mod=1e9+7; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int S = n * n - 1; vector<ll> cnt(S + 1, 0); for(int a = 1; a <= n; a++){ ll a2 = a * a; for(int b = a; b <= n; b++){ ll s = a2 + b * b; if(s > S) break; cnt[s]++; } } ll ans = 0; for(int h = 1; h <= n; h++){ ll h2 = h * h; for(int d = h + 1; d <= n; d++){ ll d2 = d * d; ll s = d2 - h2; if(s > S) continue; ans += cnt[s]; } } cout << ans << "\n"; return 0; } |