結果
問題 | No.2211 Frequency Table of GCD |
ユーザー |
|
提出日時 | 2023-02-10 21:27:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 756 bytes |
コンパイル時間 | 1,680 ms |
コンパイル使用メモリ | 167,740 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-07-07 17:51:44 |
合計ジャッジ時間 | 3,762 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long longconst int maxn=2e5+5;const int p=998244353;int cnt[maxn];int h[maxn];int po2[maxn];int32_t main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);po2[0]=1;for(int i=1;i<maxn;++i) po2[i]=(po2[i-1]*2)%p;int n,m;cin>>n>>m;int a[n];for(int i=0;i<n;++i){cin>>a[i];cnt[a[i]]++;}for(int i=1;i<maxn;++i){for(int j=i;j<maxn;j+=i){h[i]+=cnt[j];}h[i]=po2[h[i]]-1;}for(int i=maxn-1;i>=1;--i){for(int j=2*i;j<maxn;j+=i){h[i]-=h[j];h[i]%=p;}}for(int i=1;i<=m;++i){cout<<(h[i]%p+p)%p<<'\n';}return 0;}