結果
問題 |
No.2211 Frequency Table of GCD
|
ユーザー |
|
提出日時 | 2023-02-10 22:30:19 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 3,221 bytes |
コンパイル時間 | 13,537 ms |
コンパイル使用メモリ | 310,520 KB |
最終ジャッジ日時 | 2025-02-10 13:01:13 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define endl '\n' typedef long long ll; #define mod1 (ll)998244353 #define int ll #define pll pair<ll,ll> typedef long double lb; typedef tree< pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define eps (lb)(1e-9) struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; // Operator overloads template<typename T1, typename T2> // cin >> pair<T1, T2> istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); } template<typename T> // cin >> vector<T> istream& operator>>(istream &istream, vector<T> &v) { for (auto &it : v) cin >> it; return istream; } template<typename T1, typename T2> // cout << pair<T1, T2> ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); } template<typename T> // cout << vector<T> ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; } // Utility functions template <typename T> void print(T &&t) { cout << t << "\n"; } template <typename T, typename... Args> void print(T &&t, Args &&... args) { cout << t << " "; print(forward<Args>(args)...); } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll random(ll p){ // gives random number in [0,p] return uniform_int_distribution<ll>(1<<19, p)(rng); } ll power(ll a, ll b, ll c=mod1){ if(a==0){ return 0;} else if(b==0||a==1){ return 1;} ll p=power(a,b/2,c); p*=p; p%=c; if(b%2){p*=a;} p%=c; return p;} ll modinv(ll a, ll c=mod1){ return power(a,c-2,c); } ll n,m; vector<ll>freq,dp,cnt; void solve(); signed main() { io; ll t=1,n=1; // cin>>t; while (t--){ solve(); } return 0; } void solve(){ cin>>n>>m; freq.resize(m+1); freq=vector<ll>(m+1,0); dp=cnt=freq; vector<ll>v(n); cin>>v; for(auto i:v){freq[i]++;} for(ll i(1);i<=m;++i){ for(ll j(i);j<=m;j+=i){ dp[i]+=freq[j]; } } // cout<<freq<<endl; // cout<<dp<<endl; for(ll i(m);i>0;--i){ cnt[i]=power(2,dp[i])-1; for(ll j(2*i);j<=m;j+=i){ cnt[i]-=cnt[j]; } cnt[i]%=mod1; cnt[i]+=mod1; cnt[i]%=mod1; } for(ll i(1);i<=m;++i){ cout<<cnt[i]<<endl; } } // Do not get stuck on a single approach for long, think of multiple ways