結果
問題 |
No.3187 Mingle
|
ユーザー |
|
提出日時 | 2025-06-20 22:47:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,668 ms / 2,500 ms |
コード長 | 1,231 bytes |
コンパイル時間 | 5,814 ms |
コンパイル使用メモリ | 335,512 KB |
実行使用メモリ | 14,848 KB |
最終ジャッジ日時 | 2025-08-30 07:42:10 |
合計ジャッジ時間 | 41,604 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using mint = dynamic_modint<0>; int main() { int n, p; cin >> n >> p; mint::set_mod(p); vector<mint> inv(n + 1); inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = (p - p / i) * inv[p % i]; vector<int> d(n + 1, 0); for (int i = 1; i <= n; i++) for (int j = i; j <= n; j += i) d[j]++; vector sum((int)sqrt(n) + 1, vector<mint>()); for (int i = 1; i < sum.size(); i++) sum[i] = vector<mint>(n / i + 1, 0); vector<mint> dp(n + 1, 0); int sq = 1; for (int k = 3; k <= n; k++) { while ((sq + 1) * (sq + 1) <= k) sq++; mint v = 0; for (int i = 1; i <= k / sq; i++) { if (k % i == 0) continue; v += dp[k / i * i]; } for (int x = 1; x < sq; x++) { int l = k / (x + 1), r = k / x; if (k % x == 0) r--; v += sum[x][r] - sum[x][l]; } v = v * inv[k - d[k]] + k * inv[k - d[k]]; dp[k] = v; for (int x = 1; x * x <= k; x++) if (k % x == 0) sum[x][k / x] = sum[x][k / x - 1] + v; } cout << dp[n].val() << "\n"; }