結果
問題 | No.800 四平方定理 |
ユーザー | nn1k_ |
提出日時 | 2019-03-17 23:28:36 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,691 ms / 2,000 ms |
コード長 | 2,954 bytes |
コンパイル時間 | 1,009 ms |
コンパイル使用メモリ | 108,320 KB |
実行使用メモリ | 50,080 KB |
最終ジャッジ日時 | 2023-09-22 11:35:40 |
合計ジャッジ時間 | 22,547 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
4,380 KB |
testcase_01 | AC | 9 ms
4,380 KB |
testcase_02 | AC | 7 ms
4,376 KB |
testcase_03 | AC | 8 ms
4,380 KB |
testcase_04 | AC | 7 ms
4,376 KB |
testcase_05 | AC | 8 ms
4,380 KB |
testcase_06 | AC | 11 ms
4,380 KB |
testcase_07 | AC | 9 ms
4,376 KB |
testcase_08 | AC | 11 ms
4,428 KB |
testcase_09 | AC | 9 ms
4,380 KB |
testcase_10 | AC | 498 ms
26,520 KB |
testcase_11 | AC | 607 ms
28,980 KB |
testcase_12 | AC | 688 ms
28,500 KB |
testcase_13 | AC | 661 ms
27,572 KB |
testcase_14 | AC | 726 ms
28,896 KB |
testcase_15 | AC | 729 ms
28,656 KB |
testcase_16 | AC | 773 ms
28,976 KB |
testcase_17 | AC | 771 ms
28,964 KB |
testcase_18 | AC | 746 ms
29,044 KB |
testcase_19 | AC | 727 ms
28,984 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 1 ms
4,380 KB |
testcase_22 | AC | 755 ms
29,128 KB |
testcase_23 | AC | 1,691 ms
50,080 KB |
testcase_24 | AC | 1,572 ms
49,980 KB |
testcase_25 | AC | 1,541 ms
49,924 KB |
testcase_26 | AC | 1 ms
4,380 KB |
testcase_27 | AC | 2 ms
4,376 KB |
testcase_28 | AC | 1,615 ms
49,984 KB |
testcase_29 | AC | 1,498 ms
49,868 KB |
testcase_30 | AC | 1,511 ms
50,032 KB |
testcase_31 | AC | 1,423 ms
47,508 KB |
testcase_32 | AC | 1,635 ms
49,924 KB |
コンパイルメッセージ
main.cpp: 関数 ‘bool isOK(i64, i64, i64)’ 内: main.cpp:96:1: 警告: 制御が非 void 関数の終りに到達しました [-Wreturn-type] 96 | } | ^
ソースコード
#include <iostream> #include <vector> #include <map> #include <unordered_map> #include <limits> #include <algorithm> #include <queue> #include <set> #include <unordered_map> #include <numeric> #include <cmath> #include <iomanip> #include <stack> #include <string> #include <functional> using namespace std; using i64 = long long; using ui64 = unsigned long long; using P = pair<int, int>; constexpr int INF = (1 << 30); constexpr std::int64_t INF64 = (1LL << 60); constexpr int MOD = 1e9 + 7; //constexpr std::int64_t MOD64 = 1e11 + 3; int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; template <typename T, typename U> static inline std::vector<U> makeNdVector(T n, U val) noexcept { static_assert(std::is_integral<T>::value, "[makeNdVector] 1st argument must be an integer type"); return std::vector<U>(std::forward<T>(n), std::forward<U>(val)); } template <typename T, typename ...Args> static inline decltype(auto) makeNdVector(T n, Args... args) noexcept { static_assert(std::is_integral<T>::value, "[makeNdVector] 1st argument must be an integer type"); return std::vector<decltype(makeNdVector(std::forward<Args>(args)...))>(std::forward<T>(n), makeNdVector(std::forward<Args>(args)...)); } template <typename T> void print(vector<T> vec) { for (auto &e : vec) cout << e << " "; cout << endl; } void YES(bool f) { cout << (f ? "YES" : "NO") << endl; } void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; } void yes(bool f) { cout << (f ? "yes" : "no") << endl; } template <typename T> T gcd(T x, T y) { if (x == 0 || y == 0) return 0; T r; while ((r = x % y) != 0) { x = y; y = r; } return y; } template <typename T> T lcm(T x, T y) { if (x == 0 || y == 0) return 0; return (x / gcd(x, y) * y); } int next_combination(int sub) { int x = sub & -sub, y = sub + x; return (((sub & ~y) / x) >> 1) | y; } std::uint64_t combination(int n, int r) { if (n < 0 || r < 0) return 0; if (n < r) return 0; std::uint64_t k = 1; for (std::uint64_t d = 1; d <= r; ++d) { k *= n--; k /= d; } return k; } bool isOK(i64 b, i64 n, i64 key) { i64 sum = 0; while (n > 0) { sum += n % b; n /= b; } if (sum == key) return true; } i64 binary_search(i64 n, i64 key) { i64 left = -1; i64 right = n + 1; while (right - left > 1) { i64 mid = left + (right - left) / 2; long double l = log(n) / log(mid); i64 num = floor(l) + 1; cout << mid << " " << num << endl; num *= (mid - 1); if (num >= key) right = mid; else left = mid; } return right; } signed main() { cin.tie(0); ios::sync_with_stdio(false); using P = pair<int, int>; i64 N, D; cin >> N >> D; unordered_map<i64, int> left; for (i64 x = 1; x <= N; ++x) { for (i64 y = 1; y <= N; ++y) { left[x * x + y * y]++; } } i64 ans = 0; for (i64 z = 1; z <= N; ++z) { for (i64 w = 1; w <= N; ++w) { i64 n = z * z - w * w; if (left.count(D - n) == 0) continue; else ans += left[D - n]; } } cout << ans << endl; }