結果
問題 | No.2847 Birthday Attack |
ユーザー |
![]() |
提出日時 | 2024-06-27 17:08:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,928 bytes |
コンパイル時間 | 1,187 ms |
コンパイル使用メモリ | 82,300 KB |
最終ジャッジ日時 | 2025-02-22 00:47:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 2 WA * 12 |
ソースコード
#include <algorithm> #include <iostream> #include <utility> #include <vector> using namespace std; using ll = long long; using pll = pair<ll, ll>; ll mod = 998244353; ll my_gcd(ll a, ll b) { ll ret = 0; if (a < b) { swap(a, b); } if (b == 0) { ret = a; } else { ret = my_gcd(b, a % b); } return ret; } int main() { ll X, Y; cin >> X >> Y; ll ans = 0; for (ll i = 1; i <= X; i++) { ans += 2 * max(X - 2 * i, 0LL) * Y; ans %= mod; } for (ll i = 1; i <= Y; i++) { ans += 2 * max(Y - 2 * i, 0LL) * X; ans %= mod; } // ピタゴラス数を列挙する vector<pair<ll, pll>> p(0); for (ll m = 1; m * m <= 8000000; m++) { for (ll n = m + 1; n * n <= 8000000; n++) { if (m * m + n * n > 8000000) { continue; } if (m % 2 == n % 2) { continue; } ll g = my_gcd(n, m); if (g != 1) { continue; } ll min_p = 2 * m * n; ll max_p = n * n - m * m; pll pp1 = pll(min_p, max_p); pll pp2 = pll(max_p, min_p); pair<ll, pll> ppp1 = pair<ll, pll>(m * m + n * n, pp1); pair<ll, pll> ppp2 = pair<ll, pll>(m * m + n * n, pp2); p.push_back(ppp1); p.push_back(ppp2); } } sort(p.begin(), p.end()); // 列挙されたピタゴラス数の全てに対して、斜めのぶんの数え上げを行う ll len_p = p.size(); for (ll i = 0; i < len_p; i++) { ll x1 = p[i].second.first; ll y1 = p[i].second.second; for (ll j = 1; j <= min(X / y1, Y / x1); j++) { ll x = x1 * j; ll y = y1 * j; ans += 4 * max(Y - 2 * x, 0LL) * max(X - 2 * y, 0LL); ans %= mod; } } cout << ans << endl; }