結果

問題 No.2075 GCD Subsequence
ユーザー hiro71687k
提出日時 2023-03-14 12:16:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,768 ms / 4,000 ms
コード長 3,325 bytes
コンパイル時間 3,980 ms
コンパイル使用メモリ 256,064 KB
最終ジャッジ日時 2025-02-11 11:06:04
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
ld pie=3.141592653589793;
ll inf=15555055;
ll mod=998244353;
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;
}
};
int main(){
ll n;
cin >> n;
vector<ll>a(n);
for (ll i = 0; i < n; i++)
{
cin >> a[i];
}
vector<ll>memo(1000001,0);
Eratosthenes er(1000001);
ll ans=0;
memo[1]=1;
for (ll i = 0; i < n; i++)
{
if (a[i]==1)
{
ans+=1;
ans%=mod;
continue;
}
vector<ll>x=er.divisors(a[i]);
ll now=0;
for (ll j = 0; j < x.size(); j++)
{
if (x[j]==1)
{
now+=1;
now%=mod;
continue;
}
now+=(-er.mobius[x[j]]*memo[x[j]])%mod;
now%=mod;
}
now%=mod;
now+=mod;
now%=mod;
ans+=now;
ans%=mod;
for (ll j = 0; j < x.size(); j++)
{
if (x[j]!=1&&er.mobius[x[j]]!=0)
{
memo[x[j]]+=now;
memo[x[j]]%=mod;
}
}
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0