結果
問題 | No.152 貯金箱の消失 |
ユーザー |
|
提出日時 | 2017-07-27 11:10:19 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 50 ms / 5,000 ms |
コード長 | 975 bytes |
コンパイル時間 | 950 ms |
コンパイル使用メモリ | 80,372 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-10 02:03:25 |
合計ジャッジ時間 | 1,818 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<queue>#include<vector>#include<functional>#include<cmath>#include<map>#include<stack>#include<set>#include<numeric>#include<limits>#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()using namespace std;typedef long long ll;typedef pair<int, int> pi;typedef pair<ll, ll> pl;typedef pair<ll, string> pls;int gcd(int a, int b) {while (b != 0) {a = a % b;swap(a, b);}return a;}int main(){ll L; cin >> L;int mod = 1000003;ll ans = 0;for (ll i = 1; i <= L; i++) {for (ll j = i + 1; ; j++) {ll sum = i*i + j*j + 2 * i*j + j*j - i*i;if ((L - sum * 4) >= 0) {if ((j - i) % 2 != 0) {ll m[3];m[0] = i*i + j*j;m[1] = i*j * 2;m[2] = j*j - i*i;if (gcd(m[0], gcd(m[1], m[2])) == 1) {ans++;ans %= mod;}}}elsebreak;}}cout << ans << endl;return 0;}