結果
問題 | No.152 貯金箱の消失 |
ユーザー |
![]() |
提出日時 | 2015-09-24 18:15:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 783 ms / 5,000 ms |
コード長 | 1,930 bytes |
コンパイル時間 | 877 ms |
コンパイル使用メモリ | 88,988 KB |
実行使用メモリ | 17,152 KB |
最終ジャッジ日時 | 2024-07-19 09:00:51 |
合計ジャッジ時間 | 8,275 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <iostream>#include <math.h>#include <vector>#include <array>#include <algorithm>#include <queue>#include <numeric>#include <map>#include <set>#include <sstream>using namespace std;#define int long long#define FOR(i, a, b) for(int i=(a);i<(b);i++)#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)#define REP(i, n) for(int i=0; i<(n); i++)#define RREP(i, n) for(int i=(n-1); i>=0; i--)#define ALL(a) (a).begin(),(a).end()#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()#define SUM(a) accumulate(ALL(a), 0)#define array2(type, x, y) array<array<type, y>, x>#define vector2(type) vector<vector<type> >#define out(...) printf(__VA_ARGS__)typedef pair<int, int> pos;int pos::*x = &pos::first;int pos::*y = &pos::second;int dxy[] = {0, 1, 0, -1, 0};/*================================*/int L;int gcd(int a, int b) {// a > b としてwhile (a % b != 0) {int r = a % b;a = b;b = r;}return b;}signed main(){cin >> L;int maxl = L / 4;set<string> s;int cnt = 0;REP(i,4000) {FOR(n,1,(i+1)/2) {int m = i - n; // m > nを保証if (gcd(m,n) != 1) continue; // m, nは互いに素if (m-n%2 == 0) continue; // m - n は奇数vector<int> h(3);h[0] = pow(m, 2) - pow(n, 2);h[1] = 2 * m * n;h[2] = pow(m, 2) + pow(n, 2);if (SUM(h) > maxl) continue; // 長さ制限sort(ALL(h));int g = gcd(h[0], h[1]);stringstream ss;ss << h[0]/g << ":" << h[1]/g;if (s.find(ss.str()) != s.end()) continue;s.insert(ss.str());//out("%lld, %lld -> %lld, %lld, %lld\n", n, m, h[0], h[1], h[2]);cnt++;}}cout << cnt << endl;return 0;}