結果
問題 | No.152 貯金箱の消失 |
ユーザー |
|
提出日時 | 2016-05-06 22:59:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 5,000 ms |
コード長 | 840 bytes |
コンパイル時間 | 700 ms |
コンパイル使用メモリ | 74,912 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 00:31:09 |
合計ジャッジ時間 | 1,719 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>int GetGCD(int a, int b){int r=-1;if(a<b) std::swap(a, b);while(r!=0){r=a%b;a=b;b=r;}return a;}int main(){std::ios::sync_with_stdio(false);std::cin.tie(0);int l;std::cin >> l;if(l<48){std::cout << "0\n";return 0;}l/=4;std::vector<int> len;for(int m=2; m<1119; ++m){for(int n=m&1?2:1; n<m; n+=2){if(GetGCD(m, n)==1){len.push_back(2*m*(m+n));}}}std::sort(len.begin(), len.end());int mi=0, ma=len.size()-1;while(ma-mi>1){int me=(mi+ma)/2;if(l<len[me]) ma=me;else mi=me;}std::cout << ma%1000003 << "\n";return 0;}