結果
問題 | No.2211 Frequency Table of GCD |
ユーザー |
|
提出日時 | 2023-02-10 23:16:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 4,083 bytes |
コンパイル時間 | 1,162 ms |
コンパイル使用メモリ | 109,372 KB |
最終ジャッジ日時 | 2025-02-10 13:38:14 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:117:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 117 | scanf("%d %d", &N, &M); | ~~~~~^~~~~~~~~~~~~~~~~ main.cpp:119:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 119 | for(int i = 0; i < N; ++i) scanf("%d", A + i); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include<cstdio>#include<cassert>#include<vector>#include<iostream>#include<string>#include<map>#include<set>#include<stack>#include<queue>#include<functional>#include<utility>#include<cstring>#include<numeric>#include<algorithm>#include<atcoder/math>#include<atcoder/modint>//#include<ext/pb_ds/assoc_container.hpp>//#include<ext/pb_ds/tree_policy.hpp>//using namespace __gnu_pbds;using namespace std;using namespace atcoder;using ll = long long;using ull = unsigned long long;using Mint = modint998244353;using mint = modint;#define rep(i, n) for (int i = 0; i < (int)(n); ++i)#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)#define rep2(i, a, b) for (int i = (int)a; i < (int)(b); ++i)#define rrep2(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); --i)template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }constexpr int dx[] = {-1,0,1,0};constexpr int dy[] = {0,-1,0,1};constexpr int MAX_N = 100000;//ダイクストラ法:makedijkstra//エラトステネスの篩:makesieve//テストケースが複数の場合:multeststruct Eratosthenes {// テーブルvector<bool> isprime;// 整数 n を割り切る最小の素数vector<int> minfactor;// メビウス関数値vector<int> mobius;// コンストラクタで篩を回すEratosthenes(int N) : isprime(N+1, true),minfactor(N+1, -1),mobius(N+1, 1) {// 1 は予めふるい落としておくisprime[1] = false;minfactor[1] = 1;// 篩for (int p = 2; p <= N; ++p) {// すでに合成数であるものはスキップするif (!isprime[p]) continue;// p についての情報更新minfactor[p] = p;mobius[p] = -1;// p 以外の p の倍数から素数ラベルを剥奪for (int 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];}}}// 高速素因数分解、高速約数列挙は省略vector<pair<int,int>> factorize(int n) {vector<pair<int,int>> res;while (n > 1) {int p = minfactor[n];int exp = 0;// n で割り切れる限り割るwhile (minfactor[n] == p) {n /= p;++exp;}res.emplace_back(p, exp);}return res;}vector<int> divisors(int n) {vector<int> res({1});// n を素因数分解 (メンバ関数使用)auto pf = factorize(n);// 約数列挙for (auto p : pf) {int s = (int)res.size();for (int i = 0; i < s; ++i) {int v = 1;for (int j = 0; j < p.second; ++j) {v *= p.first;res.push_back(res[i] * v);}}}return res;}};int main(){//cin.tie(nullptr);//std::ios_base::sync_with_stdio(false);int N, M;scanf("%d %d", &N, &M);int A[N];for(int i = 0; i < N; ++i) scanf("%d", A + i);Eratosthenes sieve(200000);int multiple[M+1];memset(multiple, 0, sizeof(multiple));rep(i, N){auto div = sieve.divisors(A[i]);for(auto d : div){if(d > M) continue;multiple[d]++;}}Mint two[N+1];two[0] = 1;rep2(i, 1, N+1) two[i] = two[i-1]*2;Mint answer[M+1];rep2(i, 1, M+1) rep2(j, 1, M/i + 1) answer[i] += (two[multiple[i*j]] - 1)*sieve.mobius[j];rep(i, M) printf("%u\n", answer[i+1].val());return 0;}