結果
問題 | No.2211 Frequency Table of GCD |
ユーザー | hiro71687k |
提出日時 | 2023-02-27 01:18:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 491 ms / 2,000 ms |
コード長 | 3,276 bytes |
コンパイル時間 | 4,552 ms |
コンパイル使用メモリ | 264,476 KB |
実行使用メモリ | 12,696 KB |
最終ジャッジ日時 | 2023-10-12 14:32:10 |
合計ジャッジ時間 | 14,123 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
7,800 KB |
testcase_01 | AC | 24 ms
7,680 KB |
testcase_02 | AC | 25 ms
7,956 KB |
testcase_03 | AC | 298 ms
10,656 KB |
testcase_04 | AC | 284 ms
10,416 KB |
testcase_05 | AC | 357 ms
11,540 KB |
testcase_06 | AC | 324 ms
11,004 KB |
testcase_07 | AC | 400 ms
11,720 KB |
testcase_08 | AC | 50 ms
8,292 KB |
testcase_09 | AC | 44 ms
8,104 KB |
testcase_10 | AC | 80 ms
8,856 KB |
testcase_11 | AC | 64 ms
8,864 KB |
testcase_12 | AC | 85 ms
9,160 KB |
testcase_13 | AC | 266 ms
10,468 KB |
testcase_14 | AC | 347 ms
11,320 KB |
testcase_15 | AC | 311 ms
10,796 KB |
testcase_16 | AC | 342 ms
11,240 KB |
testcase_17 | AC | 345 ms
11,380 KB |
testcase_18 | AC | 478 ms
12,580 KB |
testcase_19 | AC | 469 ms
12,500 KB |
testcase_20 | AC | 468 ms
12,580 KB |
testcase_21 | AC | 467 ms
12,588 KB |
testcase_22 | AC | 477 ms
12,568 KB |
testcase_23 | AC | 324 ms
10,972 KB |
testcase_24 | AC | 491 ms
12,632 KB |
testcase_25 | AC | 57 ms
9,404 KB |
testcase_26 | AC | 25 ms
7,776 KB |
testcase_27 | AC | 466 ms
12,532 KB |
testcase_28 | AC | 490 ms
12,696 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using ld=double; ld pie=3.14159265359; ll mod=998244353; long long inf=100000000000000001; struct Eratosthenes { // テーブル vector<bool> isprime; // 整数 i を割り切る最小の素数 vector<ll> minfactor; vector<ll>mobius; // コンストラクタで篩を回す Eratosthenes(ll N) : isprime(N+1, true), minfactor(N+1, -1), mobius(N+1,1) { // 1 は予めふるい落としておく isprime[1] = false; minfactor[1] = 1; // 篩 for (ll p = 2; p <= N; ++p) { // すでに合成数であるものはスキップする if (!isprime[p]) continue; // p についての情報更新 minfactor[p] = p; mobius[p]=-1; // p 以外の p の倍数から素数ラベルを剥奪 for (ll q = p * 2; q <= N; q += p) { // q は合成数なのでふるい落とす isprime[q] = false; // q は p で割り切れる旨を更新 if (minfactor[q] == -1) minfactor[q] = p; if ((q / p) % p == 0) mobius[q] = 0; else mobius[q] = -mobius[q]; } } } // 高速素因数分解 // pair (素因子, 指数) の vector を返す vector<pair<ll,ll>> factorize(ll n) { vector<pair<ll,ll>> res; while (n > 1) { ll p = minfactor[n]; ll exp = 0; // n で割り切れる限り割る while (minfactor[n] == p) { n /= p; ++exp; } res.emplace_back(p, exp); } return res; } vector<ll>divisors(ll n){ vector<ll>res({1}); auto pf=factorize(n); for (auto p : pf) { ll s=(ll)res.size(); for (ll i = 0; i < s; i++) { ll v=1; for (ll j = 0; j < p.second; j++) { v*=p.first; res.push_back(res[i]*v); } } } return res; } }; ll modpow(ll x, ll n) { x = x%mod; if(n==0) return 1; //再帰の終了条件 else if(n%2==1) { return (x*modpow(x, n-1))%mod; //nが奇数ならnを1ずらす } else return modpow((x*x)%mod, n/2)%mod; //nが偶数ならnが半分になる } int main(){ ll n,m; cin >> n >> m; vector<ll>a(n); for (ll i = 0; i < n; i++) { cin >> a[i]; } Eratosthenes er(300000); vector<ll>memo(m+1,0); for (ll i = 0; i < n; i++) { vector<ll>x=er.divisors(a[i]); for (ll j = 0; j < x.size(); j++) { memo[x[j]]+=1; } } vector<ll>ans(m+1,0); for (ll i = m; i >=1; i--) { ll y=0; y=modpow(2,memo[i])+mod-1; y%=mod; for (ll j = 2; j*i<=m; j++) { y+=mod-ans[j*i]; y%=mod; } ans[i]=y; } for (ll i =1; i <=m; i++) { cout << ans[i] << endl; } }