結果
問題 |
No.1143 面積Nの三角形
|
ユーザー |
|
提出日時 | 2020-08-01 01:03:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 155 ms / 800 ms |
コード長 | 1,857 bytes |
コンパイル時間 | 1,839 ms |
コンパイル使用メモリ | 174,552 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-06 23:24:38 |
合計ジャッジ時間 | 3,520 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
// #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define all(x) x.begin(), x.end() #define lch (o << 1) #define rch (o << 1 | 1) typedef double db; typedef long long ll; typedef unsigned int ui; typedef pair<int, int> pint; typedef pair<ll, ll> pll; typedef tuple<int, int, int> tint; const int N = 1e6 + 5; const int INF = 0x3f3f3f3f; const ll INF_LL = 0x3f3f3f3f3f3f3f3f; bool notPri[N]; int pri[N]; void Sieve() { notPri[1] = 1; for (int i = 2; i < N; i++) { if (!notPri[i]) { pri[++pri[0]] = i; } for (int j = 1; j <= pri[0]; j++) { int p = pri[j]; if (i * p >= N) break; notPri[i * p] = 1; if (i % p == 0) break; } } } vector<pll> fac; vector<ll> divs; void GetFac(ll n) { for (int i = 1; i <= pri[0]; i++) { int p = pri[i]; if (n % p == 0) { int cnt = 0; while (n % p == 0) { n /= p; cnt++; } fac.push_back(make_pair(p, cnt)); } } } void GetDivs(int pos, ll x) { if (pos == fac.size()) { divs.push_back(x); return; } int cnt = int(fac[pos].se); for (int i = 0; i <= cnt; i++) { GetDivs(pos + 1, x); x *= fac[pos].fi; } } bool Check(ll a, ll b, ll c) { if (a <= 1 || b <= 1 || c <= 1) return 0; else return (a + b > c) && (a + c > b) && (b + c > a); } int main() { ios::sync_with_stdio(0); Sieve(); ll n; cin >> n; n = n * n; GetFac(n); GetDivs(0, 1); int ans = 0; for (auto x: divs) for (auto y: divs) { ll xyMul = x * y; ll xyAdd = x + y; if (4 * n % xyMul) continue; ll tmp1 = xyAdd * xyAdd + 4 * n / xyMul; ll rt = sqrt(tmp1); if (rt * rt != tmp1) continue; ll tmp2 = rt - xyAdd; if (tmp2 % 2 != 0) continue; ll z = tmp2 / 2; ll s = x + y + z; ll a = s - x; ll b = s - y; ll c = s - z; ans += (Check(a, b, c) && x >= y && y >= z); } cout << ans << endl; return 0; }