結果
問題 | No.152 貯金箱の消失 |
ユーザー |
![]() |
提出日時 | 2019-04-28 15:45:24 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 395 ms / 5,000 ms |
コード長 | 2,266 bytes |
コンパイル時間 | 1,805 ms |
コンパイル使用メモリ | 171,120 KB |
実行使用メモリ | 25,472 KB |
最終ジャッジ日時 | 2024-12-16 07:57:10 |
合計ジャッジ時間 | 4,230 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;using LL = long long;const LL MOD = 1e6 + 3;// 与えられた正の整数から文字列を作成して返却.// @param a: 正の整数.// @param b: 正の整数.// @param c: 正の整数.// @return ret: 生成した文字列.string exString(LL a, LL b, LL c){string ret;LL arr[2];arr[0] = a, arr[1] = b, arr[2] = c;sort(arr, arr + 2);ret = to_string(arr[0]);ret += '_';ret += to_string(arr[1]);ret += '_';ret += to_string(arr[2]);return ret;}int main() {// 1. 入力情報取得.LL L;cin >> L;// 2. 3辺を計算して, 条件に合うか確認.// m, n (m > n) を 奇数として, 以下を確認していく.// a = (m * m - n * n) / 2;// b = m * n;// c = (m * m + n * n) / 2;// -> a * a + b * b = c * c を満たしているため.LL limit = sqrt(L / 4.0) + 1;// cout << "limit=" << limit << endl;map<string, LL> rTriangle;for(LL n = 1; n <= limit; n += 2){for(LL m = n + 2; m <= limit; m += 2){LL a = (m * m - n * n) / 2;LL b = m * n;LL c = (m * m + n * n) / 2;// ex.// [入力値]// 8765// -> 182 で 不正解.// 152 が 正解とのことで,// "回転や裏返した形状のものは、同一の形状とみなします。" との問題文の指示を再確認.// ex.// m=7 n=1 a=24 b=7 c=25 と m=35 n=5 a=600 b=175 c=625 は, 同じ結果と判定する.//// a, b, c の 最大公約数で, 割ってみる.LL gcd = __gcd(a, b);gcd = __gcd(gcd, c);a /= gcd, b /= gcd, c /= gcd;string s = exString(a, b, c);if(a + b + c <= L / 4 && rTriangle[s] == 0){rTriangle[s]++;// cout << "m=" << m << " n=" << n << " a=" << a << " b=" << b << " c=" << c << " s=" << s << endl;}}}// 3. 出力 ~ 後処理.// ex.// [入力値]// 10000000// -> 175570 で, OK?LL ans = rTriangle.size();ans %= MOD;cout << ans << endl;return 0;}