結果

問題 No.152 貯金箱の消失
ユーザー @abcde@abcde
提出日時 2019-04-28 15:45:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 411 ms / 5,000 ms
コード長 2,266 bytes
コンパイル時間 1,862 ms
コンパイル使用メモリ 171,364 KB
実行使用メモリ 25,344 KB
最終ジャッジ日時 2024-05-09 17:10:59
合計ジャッジ時間 3,896 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 5 ms
5,376 KB
testcase_06 AC 7 ms
5,376 KB
testcase_07 AC 45 ms
6,912 KB
testcase_08 AC 411 ms
25,088 KB
testcase_09 AC 406 ms
25,344 KB
testcase_10 AC 297 ms
20,480 KB
testcase_11 AC 156 ms
12,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
    
}
0