#678392 (C++17) No.187 中華風 (Hard)

提出ソース

結果

問題	No.187 中華風 (Hard)
ユーザー	ytqm3
提出日時	2021-07-16 16:01:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,512 bytes
コンパイル時間	3,519 ms
コンパイル使用メモリ	245,104 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-06 03:08:54
合計ジャッジ時間	6,228 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	14 ms 6,812 KB
testcase_01	AC	14 ms 6,944 KB
testcase_02	AC	58 ms 6,940 KB
testcase_03	AC	57 ms 6,940 KB
testcase_04	AC	112 ms 6,940 KB
testcase_05	AC	112 ms 6,944 KB
testcase_06	AC	114 ms 6,944 KB
testcase_07	AC	113 ms 6,944 KB
testcase_08	AC	131 ms 6,940 KB
testcase_09	AC	130 ms 6,940 KB
testcase_10	AC	130 ms 6,940 KB
testcase_11	AC	112 ms 6,944 KB
testcase_12	AC	113 ms 6,940 KB
testcase_13	AC	76 ms 6,944 KB
testcase_14	AC	64 ms 6,940 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	12 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	92 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	113 ms 6,940 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
typedef uint64_t u64;
typedef int64_t i64;
typedef long double f128;
using namespace std;

void scan(){}

template<typename T,class... Args>
void scan(T& n,Args&... args){
  cin>>n;
  scan(args...);
}

template<typename T>
void scanall(T start,T end){
  for(;start!=end;++start){
    scan(*start);
  }
}

void print(){}

template<typename T,class... Args>
void print(T n,Args... args){
  cout<<n;
  print(args...);
}

template<typename T>
void println(T n){
  cout<<n<<endl;
}

template<typename T,class... Args>
void println(T n,Args... args){
  cout<<n<<' ';
  println(args...);
}

template<typename T>
void printall(T start,T end){
  if(start!=end){
    cout<<(*start);
    for(++start;start!=end;++start){
      cout<<' '<<(*start);
    }
  }
  cout<<endl;
}

template<typename T>
void chmax(T& n,T m){
  n=max(n,m);
}

template<typename T>
void chmin(T& n,T m){
  n=min(n,m);
}

template<typename T,typename U>
T power(T a,U n){
  T res=1;
  while(n){
    res*=((n&1)?a:1);
    a*=a;
    n>>=1;
  }
  return res;
}

i64 power(i64 a,i64 n,i64 m){
  i64 res=1%m;
  while(n){
    if(n&1){
      res=res*a%m;
    }
    a=a*a%m;
    n>>=1;
  }
  return res;
}

template<typename T>
struct combination{
  vector<T> fact,fact_inv;
  combination(int mx=3000000):fact(mx+1,1),fact_inv(mx+1,1){
    for(int i=2;i<=mx;++i){
      fact[i]=fact[i-1]*i;
    }
    fact_inv[mx]/=fact[mx];
    for(int i=mx;i>0;--i){
      fact_inv[i-1]=fact_inv[i]*i;
    }
  }
  template<typename U>
  T nCk(U n,U k){
    if(n<k||k<0){
      return 0;
    }
    return fact[n]*fact_inv[k]*fact_inv[n-k];
  }
};

template<u64 mod>
struct modint{
  u64 val;
  constexpr modint(const i64 x=0) noexcept:val((x%i64(mod)+i64(mod))%i64(mod)){}
  constexpr modint operator+(const modint rhs) const noexcept{
    return modint(*this)+=rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept{
    return modint(*this)-=rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept{
    return modint(*this)*=rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept{
    return modint(*this)/=rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept{
    val+=rhs.val;
    val-=((val>=mod)?mod:0);
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept{
    val+=((val<rhs.val)?mod:0);
    val-=rhs.val;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept{
    val=val*rhs.val%mod;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept{
    u64 exp=mod-2;
    while(exp){
      if(exp&1){
        (*this)*=rhs;
      }
      rhs*=rhs;
      exp>>=1;
    }
    return *this;
  }
  friend constexpr ostream &operator<<(ostream &os,const modint &x) noexcept{
    return os<<(x.val);
  }
  friend constexpr istream &operator>>(istream &is,modint &x) noexcept{
    u64 t;
    is>>t;
    x=t;
    return is;
  }
};

template<u64 mod>
void dft(vector<modint<mod>>& f,int inverse){
  constexpr modint<mod> g=3;
  typedef modint<mod> mint;
  i64 siz=f.size();
  if(siz==1){
    return;
  }
  vector<mint> fl(siz/2),fr(siz/2);
  for(int i=0;i<siz/2;++i){
    fl[i]=f[i*2];
    fr[i]=f[i*2+1];
  }
  dft(fl,inverse),dft(fr,inverse);
  mint zeta=power(power(g,(mod-1)/siz),inverse+mod-1),now=1;
  for(int i=0;i<siz;++i){
    f[i]=fl[i%(siz/2)]+now*fr[i%(siz/2)];
    now*=zeta;
  }
}

//mod は素数かつ原始根が 3 かつ (mod-1) が 2 でまぁまぁ割れる必要がある
template<u64 mod>
vector<modint<mod>> mul_NTTfriendlyprime(vector<modint<mod>> a,vector<modint<mod>> b){
  int siz=1,mxsiz=a.size()+b.size()-1;
  while(siz<mxsiz){
    siz*=2;
  }
  a.resize(siz),b.resize(siz);
  dft(a,1),dft(b,1);
  for(int i=0;i<siz;++i){
    a[i]*=b[i];
  }
  dft(a,-1);
  for(int i=0;i<siz;++i){
    a[i]/=siz;
  }
  a.resize(mxsiz);
  return a;
}

pair<i64,i64> ext_gcd(i64 a,i64 b){
  if(b==0){
    return {1,0};
  }
  i64 r=a%b;
  i64 x=ext_gcd(b,r).second;
  i64 y=(1-a*x)/b;
  return {x,y};
}

i64 inv_mod(i64 a,i64 m){
  assert(gcd(a,m)==1);
  return (ext_gcd(a,m).first+m)%m;
}

i64 garner(vector<i64> r,vector<i64> m,u64 mod){
  int siz=m.size();
  m.emplace_back(mod);
  vector<i64> m_prod(siz+1);
  vector<i64> x(siz+1);
  for(int i=0;i<siz+1;++i){
    m_prod[i]=1%m[i];
    x[i]=r[0]%m[i];
  }
  for(int i=0;i<siz-1;++i){
    for(int j=0;j<siz+1;++j){
      m_prod[j]=m_prod[j]*m[i]%m[j];
    }
    i64 t=(r[i+1]-x[i+1])*inv_mod(m_prod[i+1],m[i+1])%m[i+1];
    t=(t+m[i+1])%m[i+1];
    for(int j=0;j<siz+1;++j){
      x[j]=(x[j]+t*m_prod[j]%m[j])%m[j];
    }
  }
  return x[siz];
}

vector<i64> mul_anymod(vector<i64> a,vector<i64> b,u64 mod){
  constexpr u64 mod0=998244353,mod1=167772161,mod2=469762049;
  vector<modint<mod0>> a0(a.size()),b0(b.size());
  vector<modint<mod1>> a1(a.size()),b1(b.size());
  vector<modint<mod2>> a2(a.size()),b2(b.size());
  for(size_t i=0;i<a.size();++i){
    a0[i]=a[i],a1[i]=a[i],a2[i]=a[i];
  }
  for(size_t i=0;i<b.size();++i){
    b0[i]=b[i],b1[i]=b[i],b2[i]=b[i];
  }
  vector<modint<mod0>> c0=mul_NTTfriendlyprime(a0,b0);
  vector<modint<mod1>> c1=mul_NTTfriendlyprime(a1,b1);
  vector<modint<mod2>> c2=mul_NTTfriendlyprime(a2,b2);
  vector<i64> res(a.size()+b.size()-1);
  for(size_t i=0;i<res.size();++i){
    res[i]=garner({i64(c0[i].val),i64(c1[i].val),i64(c2[i].val)},{mod0,mod1,mod2},mod);
  }
  return res;
}

void solve();

int main(){
  cout<<fixed<<setprecision(15);
  bool is_multicase=false;
  int T=1;
  if(is_multicase){
    scan(T);
  }
  for(int i=0;i<T;++i){
    solve();
  }
  return 0;
}

vector<pair<int,pair<int,int>>> prime_fact(int n,int m){
  vector<pair<int,pair<int,int>>> res;
  for(int i=2;i*i<=n;++i){
    if(n%i!=0){
      continue;
    }
    int now=1;
    while(n%i==0){
      n/=i;
      now*=i;
    }
    res.push_back({i,{now,m%now}});
  }
  if(n!=1){
    res.push_back({n,{n,m%n}});
  }
  return res;
}

void solve(){
  constexpr i64 mod=1000000007;
  int N;
  scan(N);
  vector<int> X(N),Y(N);
  for(int i=0;i<N;++i){
    scan(X[i],Y[i]);
  }
  map<int,vector<pair<int,int>>> mp;
  for(int i=0;i<N;++i){
    auto ret=prime_fact(Y[i],X[i]);
    for(auto v:ret){
      mp[v.first].emplace_back(v.second);
    }
  }
  vector<i64> x,y;
  for(auto& [a,b]:mp){
    sort(b.rbegin(),b.rend());
    for(size_t i=0;i<b.size()-1;++i){
      if(b[i].second%b[i+1].first!=b[i+1].second){
        println(-1);
        return;
      }
    }
    x.emplace_back(b[0].second);
    y.emplace_back(b[0].first);
  }
  println(garner(x,y,mod));
}

yukicoder

結果

テストケース

ソースコード