結果

問題 No.2497 GCD of LCMs
ユーザー Aeren
提出日時 2023-10-06 22:24:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 118 ms / 2,000 ms
コード長 15,035 bytes
コンパイル時間 3,618 ms
コンパイル使用メモリ 282,368 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-26 16:35:35
合計ジャッジ時間 5,308 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
using namespace numbers;
using uint = unsigned int;
template<uint _mod>
struct modular_fixed_base{
static constexpr uint mod(){
return _mod;
}
template<class T>
static vector<modular_fixed_base> precalc_power(T base, int SZ){
vector<modular_fixed_base> res(SZ + 1, 1);
for(auto i = 1; i <= SZ; ++ i) res[i] = res[i - 1] * base;
return res;
}
static vector<modular_fixed_base> _INV;
static void precalc_inverse(int SZ){
if(_INV.empty()) _INV.assign(2, 1);
for(auto x = _INV.size(); x <= SZ; ++ x) _INV.push_back(_mod / x * -_INV[_mod % x]);
}
// _mod must be a prime
static modular_fixed_base _primitive_root;
static modular_fixed_base primitive_root(){
if(_primitive_root) return _primitive_root;
if(_mod == 2) return _primitive_root = 1;
if(_mod == 998244353) return _primitive_root = 3;
uint divs[20] = {};
divs[0] = 2;
int cnt = 1;
uint x = (_mod - 1) / 2;
while(x % 2 == 0) x /= 2;
for(auto i = 3; 1LL * i * i <= x; i += 2){
if(x % i == 0){
divs[cnt ++] = i;
while(x % i == 0) x /= i;
}
}
if(x > 1) divs[cnt ++] = x;
for(auto g = 2; ; ++ g){
bool ok = true;
for(auto i = 0; i < cnt; ++ i){
if((modular_fixed_base(g).power((_mod - 1) / divs[i])) == 1){
ok = false;
break;
}
}
if(ok) return _primitive_root = g;
}
}
constexpr modular_fixed_base(): data(){ }
modular_fixed_base(const double &x){ data = normalize(llround(x)); }
modular_fixed_base(const long double &x){ data = normalize(llround(x)); }
template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base(const T &x){ data = normalize(x); }
template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> static uint normalize(const T &x){
int sign = x >= 0 ? 1 : -1;
uint v = _mod <= sign * x ? sign * x % _mod : sign * x;
if(sign == -1 && v) v = _mod - v;
return v;
}
const uint &operator()() const{ return data; }
template<class T> operator T() const{ return data; }
modular_fixed_base &operator+=(const modular_fixed_base &otr){ if((data += otr.data) >= _mod) data -= _mod; return *this; }
modular_fixed_base &operator-=(const modular_fixed_base &otr){ if((data += _mod - otr.data) >= _mod) data -= _mod; return *this; }
template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base &operator+=(const T &otr){ return *this +=
        modular_fixed_base(otr); }
template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base &operator-=(const T &otr){ return *this -=
        modular_fixed_base(otr); }
modular_fixed_base &operator++(){ return *this += 1; }
modular_fixed_base &operator--(){ return *this += _mod - 1; }
modular_fixed_base operator++(int){ modular_fixed_base result(*this); *this += 1; return result; }
modular_fixed_base operator--(int){ modular_fixed_base result(*this); *this += _mod - 1; return result; }
modular_fixed_base operator-() const{ return modular_fixed_base(_mod - data); }
modular_fixed_base &operator*=(const modular_fixed_base &rhs){
data = (unsigned long long)data * rhs.data % _mod;
return *this;
}
template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr>
modular_fixed_base &inplace_power(T e){
if(!data) return *this = {};
if(data == 1) return *this;
if(data == mod() - 1) return e % 2 ? *this : *this = -*this;
if(e < 0) *this = 1 / *this, e = -e;
modular_fixed_base res = 1;
for(; e; *this *= *this, e >>= 1) if(e & 1) res *= *this;
return *this = res;
}
template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr>
modular_fixed_base power(T e) const{
return modular_fixed_base(*this).inplace_power(e);
}
modular_fixed_base &operator/=(const modular_fixed_base &otr){
int a = otr.data, m = _mod, u = 0, v = 1;
if(a < _INV.size()) return *this *= _INV[a];
while(a){
int t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return *this *= u;
}
uint data;
};
template<uint _mod> vector<modular_fixed_base<_mod>> modular_fixed_base<_mod>::_INV;
template<uint _mod> modular_fixed_base<_mod> modular_fixed_base<_mod>::_primitive_root;
template<uint _mod> bool operator==(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data == rhs.data; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator==(const modular_fixed_base<_mod> &lhs, T rhs){
    return lhs == modular_fixed_base<_mod>(rhs); }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator==(T lhs, const modular_fixed_base<_mod> &rhs){
    return modular_fixed_base<_mod>(lhs) == rhs; }
template<uint _mod> bool operator!=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return !(lhs == rhs); }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator!=(const modular_fixed_base<_mod> &lhs, T rhs){
    return !(lhs == rhs); }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator!=(T lhs, const modular_fixed_base<_mod> &rhs){
    return !(lhs == rhs); }
template<uint _mod> bool operator<(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data < rhs.data; }
template<uint _mod> bool operator>(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data > rhs.data; }
template<uint _mod> bool operator<=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data <= rhs.data; }
template<uint _mod> bool operator>=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data >= rhs.data; }
template<uint _mod> modular_fixed_base<_mod> operator+(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return
    modular_fixed_base<_mod>(lhs) += rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator+(const modular_fixed_base
    <_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) += rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator+(T lhs, const
    modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) += rhs; }
template<uint _mod> modular_fixed_base<_mod> operator-(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return
    modular_fixed_base<_mod>(lhs) -= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator-(const modular_fixed_base
    <_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) -= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator-(T lhs, const
    modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) -= rhs; }
template<uint _mod> modular_fixed_base<_mod> operator*(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return
    modular_fixed_base<_mod>(lhs) *= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator*(const modular_fixed_base
    <_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) *= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator*(T lhs, const
    modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) *= rhs; }
template<uint _mod> modular_fixed_base<_mod> operator/(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs) { return
    modular_fixed_base<_mod>(lhs) /= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator/(const modular_fixed_base
    <_mod> &lhs, T rhs) { return modular_fixed_base<_mod>(lhs) /= rhs; }
template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator/(T lhs, const
    modular_fixed_base<_mod> &rhs) { return modular_fixed_base<_mod>(lhs) /= rhs; }
template<uint _mod> istream &operator>>(istream &in, modular_fixed_base<_mod> &number){
long long x;
in >> x;
number.data = modular_fixed_base<_mod>::normalize(x);
return in;
}
// #define _SHOW_FRACTION
template<uint _mod> ostream &operator<<(ostream &out, const modular_fixed_base<_mod> &number){
out << number();
#if defined(LOCAL) && defined(_SHOW_FRACTION)
cerr << "(";
for(auto d = 1; ; ++ d){
if((number * d).data <= 1000000){
cerr << (number * d).data;
if(d != 1) cerr << "/" << d;
break;
}
else if((-number * d).data <= 1000000){
cerr << "-" << (-number * d).data;
if(d != 1) cerr << "/" << d;
break;
}
}
cerr << ")";
#endif
return out;
}
#undef _SHOW_FRACTION
// const uint mod = 1e9 + 7; // 1000000007
const uint mod = (119 << 23) + 1; // 998244353
// const uint mod = 1e9 + 9; // 1000000009
using modular = modular_fixed_base<mod>;
template<class T>
struct graph{
struct E{
int from, to;
T cost;
};
int n;
vector<E> edge;
vector<vector<int>> adj;
function<bool(int)> ignore;
graph(int n = 1): n(n), adj(n){
assert(n >= 1);
}
graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
}
else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
}
graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
}
else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
}
graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
}
graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
}
int operator()(int u, int id) const{
#ifdef LOCAL
assert(0 <= id && id < (int)edge.size());
assert(edge[id].from == u || edge[id].to == u);
#endif
return u ^ edge[id].from ^ edge[id].to;
}
int link(int u, int v, T w = {}){ // insert an undirected edge
int id = (int)edge.size();
adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
return id;
}
int orient(int u, int v, T w = {}){ // insert a directed edge
int id = (int)edge.size();
adj[u].push_back(id), edge.push_back({u, v, w});
return id;
}
void clear(){
for(auto [u, v, w]: edge){
adj[u].clear();
adj[v].clear();
}
edge.clear();
ignore = {};
}
graph transposed() const{ // the transpose of the directed graph
graph res(n);
for(auto &e: edge) res.orient(e.to, e.from, e.cost);
res.ignore = ignore;
return res;
}
int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
return (int)adj[u].size();
}
// The adjacency list is sorted for each vertex.
vector<vector<int>> get_adjacency_list() const{
vector<vector<int>> res(n);
for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
if(ignore && ignore(id)) continue;
res[(*this)(u, id)].push_back(u);
}
return res;
}
void set_ignoration_rule(const function<bool(int)> &f){
ignore = f;
}
void reset_ignoration_rule(){
ignore = nullptr;
}
friend ostream &operator<<(ostream &out, const graph &g){
for(auto id = 0; id < (int)g.edge.size(); ++ id){
if(g.ignore && g.ignore(id)) continue;
auto &e = g.edge[id];
out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
}
return out;
}
};
template<bool Enable_small_to_large = true>
struct disjoint_set{
int n, _classes;
vector<int> p;
disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
int make_set(){
p.push_back(-1);
++ _classes;
return n ++;
}
int classes() const{
return _classes;
}
int root(int u){
return p[u] < 0 ? u : p[u] = root(p[u]);
}
bool share(int a, int b){
return root(a) == root(b);
}
int size(int u){
return -p[root(u)];
}
bool merge(int u, int v){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u;
return true;
}
bool merge(int u, int v, auto act){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
bool swapped = false;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
p[u] += p[v], p[v] = u;
act(u, v, swapped);
return true;
}
void clear(){
_classes = n;
fill(p.begin(), p.end(), -1);
}
vector<vector<int>> group_up(){
vector<vector<int>> g(n);
for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
return g;
}
};
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(ios::badbit | ios::failbit);
int n, m;
cin >> n >> m;
vector<int> a(n);
copy_n(istream_iterator<int>(cin), n, a.begin());
graph<int> g(n);
for(auto i = 0; i < m; ++ i){
int u, v;
cin >> u >> v, -- u, -- v;
g.link(u, v, 1);
}
map<int, vector<int>> appear;
for(auto u = 0; u < n; ++ u){
int x = a[u];
for(auto p = 2; p * p <= x; ++ p){
if(x % p == 0){
if(!appear.contains(p)){
appear[p] = vector<int>(n);
}
int e = 0;
while(x % p == 0){
x /= p;
++ e;
}
appear[p][u] = e;
}
}
if(x >= 2){
if(!appear.contains(x)){
appear[x] = vector<int>(n);
}
appear[x][u] = 1;
}
}
vector<modular> res(n, 1);
for(auto [p, e]: appear){
auto power = modular::precalc_power(p, 100);
static vector<int> order(n);
iota(order.begin(), order.end(), 0);
ranges::sort(order, [&](int u, int v){ return e[u] < e[v]; });
static disjoint_set dsu(n);
dsu.clear();
static vector<int> was(n), active(n);
active[0] = p;
res[0] *= power[e[0]];
for(auto u: order){
was[u] = p;
for(auto id: g.adj[u]){
int v = g(u, id);
if(was[v] != p || !dsu.merge(u, v)){
continue;
}
for(auto w = 0; w < n; ++ w){
if(dsu.share(0, w) && active[w] != p){
active[w] = p;
res[w] *= power[e[u]];
}
}
}
}
}
ranges::copy(res, ostream_iterator<modular>(cout, "\n"));
return 0;
}
/*
*/
////////////////////////////////////////////////////////////////////////////////////////
// //
// Coded by Aeren //
// //
////////////////////////////////////////////////////////////////////////////////////////
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0