結果
問題 | No.2211 Frequency Table of GCD |
ユーザー |
![]() |
提出日時 | 2023-02-10 22:17:22 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 786 bytes |
コンパイル時間 | 588 ms |
コンパイル使用メモリ | 29,824 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-07 18:04:54 |
合計ジャッジ時間 | 2,716 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <stdio.h>int main () {int n = 0;int m = 0;int a = 0;int res = 0;long long ans[200001] = {};long long mod_num = 998244353LL;int cnt[200001] = {};int pow2[200001] = {};res = scanf("%d", &n);res = scanf("%d", &m);for (int i = 0; i < n; i++) {res = scanf("%d", &a);cnt[a]++;}pow2[0] = 1LL;for (int i = 0; i < n; i++) {pow2[i+1] = (pow2[i]<<1LL)%mod_num;}for (int i = m; i > 0; i--) {int mcnt = 0;for (int p = 1; p*i <= m; p++) {mcnt += cnt[p*i];}ans[i] = mod_num-1LL+pow2[mcnt];for (int p = 2; p*i <= m; p++) {ans[i] += mod_num-ans[p*i];}ans[i] %= mod_num;}for (int i = 0; i < m; i++) {printf("%lld\n", ans[i+1]);}return 0;}