結果

問題 No.152 貯金箱の消失
コンテスト
ユーザー @abcde
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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