結果
問題 | No.2963 Mecha DESU |
ユーザー |
![]() |
提出日時 | 2024-11-16 16:23:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 290 ms / 2,000 ms |
コード長 | 925 bytes |
コンパイル時間 | 5,199 ms |
コンパイル使用メモリ | 309,376 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-11-16 16:23:53 |
合計ジャッジ時間 | 14,425 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include <bits/stdc++.h> using namespace std; using namespace chrono; #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif int main() { int64_t n, m, k; cin >> n >> m >> k; vector<int64_t> as(m); for (auto &&a : as) { cin >> a; } vector<int64_t> bs(10); vector<int64_t> cnt(1000001); for (auto &&a : as) { if (a < 10) { bs[a]++; continue; } for (int64_t i = a; i <= 1000000; i += a) { cnt[i]++; } } for (int64_t a = 1; a < 10; a++) { for (int64_t i = a; i <= 1000000; i += a) { cnt[i] += bs[a]; } } using mint = modint998244353; mint ans = 0; for (int64_t i = 1; i <= n; i++) { ans += 1 - (mint(m - cnt[i]) / m).pow(k); } cout << ans.val() << endl; return 0; }