結果

問題 No.2211 Frequency Table of GCD
ユーザー hari64hari64
提出日時 2023-02-10 21:45:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,460 ms / 2,000 ms
コード長 8,111 bytes
コンパイル時間 2,687 ms
コンパイル使用メモリ 222,620 KB
実行使用メモリ 15,056 KB
最終ジャッジ日時 2023-09-22 01:02:39
合計ジャッジ時間 26,057 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 855 ms
12,948 KB
testcase_04 AC 722 ms
10,580 KB
testcase_05 AC 955 ms
11,704 KB
testcase_06 AC 954 ms
12,156 KB
testcase_07 AC 1,180 ms
13,552 KB
testcase_08 AC 9 ms
4,384 KB
testcase_09 AC 8 ms
4,376 KB
testcase_10 AC 18 ms
4,376 KB
testcase_11 AC 13 ms
4,376 KB
testcase_12 AC 19 ms
4,376 KB
testcase_13 AC 674 ms
10,268 KB
testcase_14 AC 1,116 ms
13,260 KB
testcase_15 AC 956 ms
12,496 KB
testcase_16 AC 1,054 ms
13,020 KB
testcase_17 AC 952 ms
11,748 KB
testcase_18 AC 1,371 ms
14,608 KB
testcase_19 AC 1,345 ms
14,532 KB
testcase_20 AC 1,400 ms
14,608 KB
testcase_21 AC 1,456 ms
15,012 KB
testcase_22 AC 1,460 ms
15,056 KB
testcase_23 AC 1,189 ms
13,740 KB
testcase_24 AC 1,209 ms
14,952 KB
testcase_25 AC 13 ms
4,376 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 1,240 ms
14,604 KB
testcase_28 AC 1,195 ms
14,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef hari64
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#define debug(...)
#else
#include "util/viewer.hpp"
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif
using namespace std;
constexpr int INF = 1001001001;
constexpr long long INFll = 1001001001001001001;
template <class T>
bool chmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}

// clang-format off
namespace internal{template<class T>using is_signed_int128=typename conditional<is_same<T,__int128_t>::value||is_same<T,__int128>::value,true_type,false_type>::type;template<class T>using is_unsigned_int128=typename conditional<is_same<T,__uint128_t>::value||is_same<T,unsigned __int128>::value,true_type,false_type>::type;template<class T>using is_integral=typename conditional<std::is_integral<T>::value||is_signed_int128<T>::value||is_unsigned_int128<T>::value,true_type,false_type>::type;
template<class T>using is_signed_int=typename conditional<(is_integral<T>::value&&is_signed<T>::value)||is_signed_int128<T>::value,true_type,false_type>::type;template<class T>using is_unsigned_int=typename conditional<(is_integral<T>::value&&is_unsigned<T>::value)||is_unsigned_int128<T>::value,true_type,false_type>::type;template<class T>using is_signed_int_t=enable_if_t<is_signed_int<T>::value>;template<class T>using is_unsigned_int_t=enable_if_t<is_unsigned_int<T>::value>;
constexpr long long safe_mod(long long x,long long m){x%=m;if(x<0)x+=m;return x;}struct barrett{unsigned int _m;unsigned long long im;explicit barrett(unsigned int m):_m(m),im((unsigned long long)(-1)/m+1){}unsigned int umod()const{return _m;}unsigned int mul(unsigned int a,unsigned int b)const{unsigned long long z=a;z*=b;unsigned long long x=(unsigned long long)(((unsigned __int128)(z)*im)>>64);unsigned int v=(unsigned int)(z-x*_m);if(_m<=v)v+=_m;return v;}};
constexpr long long pow_mod_constexpr(long long x,long long n,int m){if(m==1)return 0;unsigned int _m=(unsigned int)(m);unsigned long long r=1;unsigned long long y=safe_mod(x,m);while(n){if(n&1)r=(r*y)%_m;y=(y*y)%_m;n>>=1;}return r;}constexpr pair<long long,long long>inv_gcd(long long a,long long b){a=safe_mod(a,b);if(a==0)return{b,0};long long s=b,t=a;long long m0=0,m1=1;while(t){long long u=s/t;s-=t*u;m0-=m1*u;auto tmp=s;s=t;t=tmp;tmp=m0;m0=m1;m1=tmp;}if(m0<0)m0+=b/s;return{s,m0};}
constexpr bool is_prime_constexpr(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long long d=n-1;while(d%2==0)d/=2;constexpr long long bases[3]={2,7,61};for(long long a:bases){long long t=d;long long y=pow_mod_constexpr(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0)return false;}return true;}template<int n>constexpr bool is_prime=is_prime_constexpr(n);} // namespace internal
template<int m>struct static_modint{using mint=static_modint;static constexpr int mod(){return m;}static mint raw(int v){mint x;x._v=v;return x;}static_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>static_modint(T v){long long x=(long long)(v%(long long)(umod()));if(x<0)x+=umod();_v=(unsigned int)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>static_modint(T v){_v=(unsigned int)(v%umod());}unsigned int val()const{return _v;}
mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint&rhs){_v-=rhs._v;if(_v>=umod())_v+=umod();return*this;}
mint&operator*=(const mint&rhs){unsigned long long z=_v;z*=rhs._v;_v=(unsigned int)(z%umod());return*this;}mint&operator/=(const mint&rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(long long n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{if(prime){assert(_v);return pow(umod()-2);}else{auto eg=internal::inv_gcd(_v,m);assert(eg.first==1);return eg.second;}}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}
friend ostream&operator<<(ostream&os,const mint&rhs){return os<<rhs._v;}friend istream&operator>>(istream&is,mint&rhs){long long v;is>>v;v%=(long long)(umod());if(v<0)v+=umod();;rhs._v=(unsigned int)v;return is;}static constexpr bool prime=internal::is_prime<m>;private:unsigned int _v;static constexpr unsigned int umod(){return m;}};
constexpr int MOD = 998244353;using mint=static_modint<MOD>;vector<mint>mint_factorial={mint(1)};/*n>1e8 ⇒ fast_modfact(deprecated)*/mint modfact(int n){assert(n<=100000000);if(int(mint_factorial.size())<=n){for(int i=mint_factorial.size();i<=n;i++){mint next=mint_factorial.back()*i;mint_factorial.push_back(next);}}return mint_factorial[n];}
/*x s.t. x^2 ≡ a (mod Prime) or -1*/mint modsqrt(mint a){long long p=mint::mod();if(a.val()==1)return a;if(a.pow((p-1)>>1).val()!=1)return -1;mint b=1,one=1;while(b.pow((p-1)>>1).val()==1)b+=one;long long m=p-1,e=0;while(m%2==0)m>>=1,e++;mint x=a.pow((m-1)>>1);mint y=a*x*x;x*=a;mint z=b.pow(m);while(y!=1){long long j=0;mint t=y;while(t!=one)j++,t*=t;z=z.pow(1ll<<(e-j-1));x*=z;z*=z;y*=z;e=j;}return x;}mint nCk(int n,int k){if(k<0||n<k)return mint(0);return modfact(n)*(modfact(k)).inv()*modfact(n-k).inv();}
/*min x s.t. a^x ≡ b (mod M) or -1*/int modlog(mint a,mint b){if(gcd(a.mod(),a.val())!=1){cout<<"\033[1;31mCAUTION: m must be coprime to a.\033[0m"<<endl;assert(false);}long long m=mint::mod();long long sq=round(sqrt(m))+1;unordered_map<long long,long long>ap;mint re=a;for(long long r=1;r<sq;r++){if(ap.find(re.val())==ap.end())ap[re.val()]=r;re*=a;}mint A=a.inv().pow(sq);re=b;for(mint q=0;q.val()<sq;q++){if(re==1&&q!=0)return(q*sq).val();if(ap.find(re.val())!=ap.end())return(q*sq+ap[re.val()]).val();re*=A;}return-1;};
// clang-format on

// O(NloglogN)
vector<bool> prime_table(int n) {
    assert(n >= 1);
    vector<bool> isp(n + 1, false);
    if (n == 1) return isp;
    isp[2] = 1;
    for (int i = 3; i <= n; i += 2) isp[i] = true;
    for (int p = 3; p * p <= n; p += 2)
        if (isp[p])
            for (int q = p * p; q <= n; q += (p << 1)) isp[q] = false;
    return isp;
}

// mobius[1]=1 (mobius[0] is undefined, but it also has 1)
// mobius[n]=0 if ∃p s.t. (p^2)|n
// mobius[n]=(-1)^K when n=Π_{k=1}^{K} p_k
// note that f[1] = Σ_{n} μ[n]*F[n] where F[n] = Σ_{n|i} f[i]
vector<int> mobius_table(int n, const vector<bool>& isp) {
    vector<int> mobius(n + 1, 1);
    for (int p = 2; p <= n; p++)
        if (isp[p]) {
            for (int j = p; j <= n; j += p) mobius[j] *= -1;
            if (p <= n / p)
                for (int j = p * p; j <= n; j += p * p) mobius[j] = 0;
        }
    return mobius;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    vector<int> mobius = mobius_table(M, prime_table(M));

    map<int, int> cnt;
    vector<int> As(N);
    for (int i = 0; i < N; i++) {
        cin >> As[i];
        cnt[As[i]]++;
    }
    vector<mint> table(M + 1);
    for (int i = 1; i <= M; i++) {
        for (int j = i; j <= M; j += i) {
            table[i] += cnt[j];
        }
        table[i] = mint(2).pow(table[i].val()) - 1;
    }

    debug(table);
    debug(mobius);

    for (int i = 1; i <= M; i++) {
        mint ans = 0;
        for (int j = i; j <= M; j += i) {
            ans += mobius[j / i] * table[j];
        }
        cout << ans << endl;
    }

    return 0;
}
0