結果
| 問題 |
No.3187 Mingle
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-06-20 22:37:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 506 ms / 2,500 ms |
| コード長 | 1,199 bytes |
| コンパイル時間 | 1,856 ms |
| コンパイル使用メモリ | 198,868 KB |
| 実行使用メモリ | 40,596 KB |
| 最終ジャッジ日時 | 2025-06-20 22:37:55 |
| 合計ジャッジ時間 | 11,684 ms |
|
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, P;
cin >> N >> P;
vector<int> d(N + 1, 0);
vector<vector<int>> divs(N + 1);
for (int b = 1; b <= N; ++b) {
for (int m = b; m <= N; m += b) {
d[m]++;
divs[m].push_back(b);
}
}
vector<int> inv(N + 2, 0);
inv[1] = 1;
for (int i = 2; i <= N + 1; ++i) {
inv[i] = int64(P - P / i) * inv[P % i] % P;
}
vector<int> diff(N + 2, 0);
int64 curF = 0;
vector<int> E(N + 1, 0);
for (int m = 1; m <= N; ++m) {
curF = (curF + diff[m]) % P;
if (m >= 3) {
int64 numer = (m + curF) % P;
int denom = m - d[m];
E[m] = numer * inv[denom] % P;
}
int em = E[m];
if (em) {
for (int b : divs[m]) {
int L = m + 1;
int R = min(N, m + b - 1);
if (L > R) continue;
diff[L] = (diff[L] + em) % P;
diff[R + 1] = (diff[R + 1] - em + P) % P;
}
}
}
cout << E[N] << "\n";
return 0;
}