結果

問題 No.152 貯金箱の消失
コンテスト
ユーザー erbowl
提出日時 2025-01-30 08:58:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 319 ms / 5,000 ms
コード長 1,989 bytes
コンパイル時間 5,525 ms
コンパイル使用メモリ 324,720 KB
実行使用メモリ 15,076 KB
最終ジャッジ日時 2025-01-30 08:58:15
合計ジャッジ時間 5,848 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

typedef long long ll;
typedef long double ld;

#include <bits/stdc++.h>
using namespace std;
// #define int long long

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// std::cout << *s.find_by_order(1) << std::endl; // 2

signed main()
{
    // これがないと落ちることがある
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll l;
    cin >> l;
    const ll MOD = 1000003;
    l /= 4;
    ll ans = 0;
    vector<ll> hei;
    for (ll i = 1; i < 100000; i++)
    {
        hei.push_back(i * i);
    }

    set<tuple<ll, ll, ll>> s;

    for (ll i = 1; 4 * i * i <= l; i++)
    {
        for (ll j = i + 1; 2 * j * j + 2 * j * i <= l; j++)
        {
            ll a, b, c = 0;
            a = j * j - i * i;
            b = 2 * j * i;
            c = j * j + i * i;
            ll g = gcd(gcd(a, b), c);
            vector<ll> t;
            t.push_back(a);
            t.push_back(b);
            t.push_back(c);
            sort(t.begin(), t.end());
            a = t[0];
            b = t[1];
            c = t[2];

            s.insert({a / g, b / g, c / g});
        }
        // ll le = i + 1;
        // ll r = 1e9;
        // cout << le * le - i * i << " " << 2 * le * i << " " << le * le + i * i << endl;
        // if (2 * le * le + 2 * le * i > l)
        //     break;
        // while (r - le > 1)
        // {
        //     ll m = (r + le) / 2;
        //     if (2 * m * m + 2 * m * i <= l)
        //     {
        //         le = m;
        //     }
        //     else
        //     {
        //         r = m;
        //     }
        // }
        // ans += max(0ll, le - i);
        // cout << i << " " << le << " " << ans << endl;
    }
    // for (auto e : s)
    // {
    //     auto [a, b, c] = e;
    //     cout << a << " " << b << " " << c << endl;
    // }
    cout << s.size() % MOD << endl;
}
0