結果

問題 No.152 貯金箱の消失
ユーザー @abcde@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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0