結果
| 問題 |
No.2264 Gear Coloring
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2023-04-07 22:20:15 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 155 ms / 2,000 ms |
| コード長 | 8,649 bytes |
| コンパイル時間 | 1,512 ms |
| コンパイル使用メモリ | 96,216 KB |
| 最終ジャッジ日時 | 2025-02-12 01:42:26 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 18 |
ソースコード
#line 1 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\enumerate-divisors.hpp"
#include <vector>
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\isprime.hpp"
#include <initializer_list>
namespace nachia{
bool IsPrime(unsigned long long x) noexcept {
if(x <= 1) return false;
if(x % 2 == 0) return x == 2;
using u64 = unsigned long long;
using u128 = __uint128_t;
u64 d = x-1;
int s = 0;
int q = 63;
while(!(d&1)){ d >>= 1; s++; }
while(!(d >> q)) q--;
u64 r = x; for(int t=0; t<6; t++) r*=2-r*x;
u128 n2 = -(u128)x % x;
auto red = [=](u128 t) noexcept -> u64 {
t = (t + (u128)((u64)t*-r)*x) >> 64;
return (t >= x) ? t-x : t;
};
u64 one = red(n2);
for(u64 base : { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }){
if(base%x==0) continue;
u64 a = base = red(base%x*n2);
for(int e=q-1; e>=0; e--){ a = red((u128)a*a); if((d>>e)&1) a = red((u128)a*base); }
if(a == one) continue;
for(int t=1; t<s&&a!=x-one; t++) a = red((u128)a*a);
if(a != x-one) return false;
}
return true;
}
} // namespace nachia
#line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\misc\\bit-operations.hpp"
#include <algorithm>
namespace nachia{
int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
return __builtin_popcountll(c);
#else
c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
c = (c * (~0ull/257)) >> 56;
return c;
#endif
}
// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return 63 - __builtin_clzll(x);
#else
int res = 0;
for(int d=32; d>0; d>>=1) if(x >> d){ res |= d; x >>= d; }
return res;
#endif
}
// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return __builtin_ctzll(x);
#else
return MsbIndex(x & -x);
#endif
}
}
#line 5 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\factorize.hpp"
#include <utility>
namespace nachia{
std::vector<std::pair<unsigned long long, int>> Factorize(unsigned long long x){
if(x == 1) return {};
if(IsPrime(x)) return {{x,1}};
using u64 = unsigned long long;
using u128 = __uint128_t;
u64 X = x;
std::vector<u64> p;
for(u64 i=2; i<100; i+=1+i%2) if(x%i==0){ p.push_back(i); while(x%i==0) x/=i; }
u64 r=1; u128 n2=1;
auto updX = [&](){
r = x; for(int t=0; t<6; t++) r*=2-r*x;
n2 = -(u128)x % x;
};
auto red = [&](u128 t) noexcept -> u64 {
u64 s = ((u128)x*((u64)t*r)) >> 64;
u64 t2 = t >> 64;
return t2-s + (t2 < s ? x : 0);
};
auto mult = [&](u64 a, u64 b) noexcept { return red((u128)red((u128)a*n2)*b); };
auto gcd = [](u64 a, u64 b) noexcept {
if(!a || !b) return a|b;
int q = LsbIndex(a|b);
b >>= LsbIndex(b);
a >>= LsbIndex(a);
while(a!=b){
if(a<b){ b-=a; b>>=LsbIndex(b); }
else{ a-=b; a>>=LsbIndex(a); }
}
return a<<q;
};
static u64 v = 7001;
p.push_back(x);
for(int pi=p.size()-1; pi<(int)p.size(); pi++) while(p[pi] != 1 && !IsPrime(p[pi])){
x = p[pi]; updX();
while(p[pi] == x){
v^=v<<13; v^=v>>7; v^=v<<17; // Xorshift https://www.jstatsoft.org/article/download/v008i14/916
u64 c = red(v); if(c == 0) continue;
auto f = [=](u64 a) noexcept -> u64 { return red((u128)a*a+c); };
u64 a=0, b=f(a);
u64 buf = 1, sz = 1, nx = 10;
while(true){
while(nx != sz && a != b){
buf = mult(buf, a<=b?b-a:a-b); sz++;
a = f(a); b = f(f(b));
}
u64 g = gcd(buf, x);
if(g != 1){
while(p[pi] % g == 0) p[pi] /= g;
p.push_back(g);
break;
}
if(a == b) break;
nx = sz * 3 / 2;
}
}
}
std::vector<std::pair<u64, int>> res;
for(u64 q : p) if(q != 1){
int e=0; while(X%q == 0){ e++; X/=q; }
if(e) res.push_back({ q, e });
}
return res;
}
unsigned long long Totient(unsigned long long x){
auto F = Factorize(x);
for(auto f : F) x -= x / f.first;
return x;
}
} // namespace nachia
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\gcd.hpp"
#line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\gcd.hpp"
namespace nachia{
template<class Int> Int Gcd(Int a, Int b){
if(a < 0) a = -a;
if(b < 0) b = -b;
if(!a || !b) return a + b;
while(b){ a %= b; std::swap(a, b); }
return a;
}
}
#line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\enumerate-divisors.hpp"
namespace nachia{
struct EnumerateDivisors{
using u64 = unsigned long long;
u64 raw;
std::vector<u64> divord;
std::vector<int> dims;
std::vector<int> dimcum;
std::vector<std::pair<u64, int>> I;
EnumerateDivisors(std::vector<std::pair<unsigned long long, int>> pf){
raw = 1;
int n = pf.size();
dims.resize(n);
dimcum.assign(n+1, 1);
divord = {1};
for(int i=0; i<n; i++){
dims[i] = pf[i].second;
dimcum[i+1] = dimcum[i] * (dims[i] + 1);
int q = dimcum[i];
for(int t=q; t<dimcum[i+1]; t++) divord.push_back(divord[t-q] * pf[i].first);
for(int t=0; t<pf[i].second; t++) raw *= pf[i].first;
}
I.resize(divord.size());
for(int i=0; i<dimcum.back(); i++) I[i] = std::make_pair(divord[i], i);
std::sort(I.begin(), I.end());
}
int id(unsigned long long d) const {
d = Gcd(d, raw);
return std::lower_bound(I.begin(), I.end(), d, [](std::pair<u64, int> e, u64 v){ return e.first < v; })->second;
}
int numDivisors() const { return dimcum.back(); }
unsigned long long divisor(int i){ return divord[i]; }
template<class Elem>
void Zeta(std::vector<Elem>& A) const {
int Z = numDivisors();
for(int d=0; d<(int)dims.size(); d++){
int w = dims[d] * dimcum[d];
int y = dimcum[d];
for(int i=0; i<Z; i+=dimcum[d+1]){
for(int j=0; j<w; j++) A[i+j+y] += A[i+j];
}
}
}
template<class Elem>
void RevZeta(std::vector<Elem>& A) const {
int Z = numDivisors();
for(int d=0; d<(int)dims.size(); d++){
int w = dims[d] * dimcum[d];
int y = dimcum[d];
for(int i=0; i<Z; i+=dimcum[d+1]){
for(int j=w-1; j>=0; j--) A[i+j] += A[i+j+y];
}
}
}
template<class Elem>
void Mobius(std::vector<Elem>& A) const {
int Z = numDivisors();
for(int d=0; d<(int)dims.size(); d++){
int w = dims[d] * dimcum[d];
int y = dimcum[d];
for(int i=0; i<Z; i+=dimcum[d+1]){
for(int j=w-1; j>=0; j--) A[i+j+y] -= A[i+j];
}
}
}
template<class Elem>
void RevMobius(std::vector<Elem>& A) const {
int Z = numDivisors();
for(int d=0; d<(int)dims.size(); d++){
int w = dims[d] * dimcum[d];
int y = dimcum[d];
for(int i=0; i<Z; i+=dimcum[d+1]){
for(int j=0; j<w; j++) A[i+j] -= A[i+j+y];
}
}
}
};
}
#line 2 "..\\Main.cpp"
#include <iostream>
#include <string>
#line 7 "..\\Main.cpp"
#include <atcoder/modint>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;
int main(){
int N, M; cin >> N >> M;
vector<i64> A(N); rep(i,N) cin >> A[i];
i64 lcm = 1;
for(i64 a : A) lcm = lcm / nachia::Gcd(lcm, a) * a;
auto divs = nachia::EnumerateDivisors(nachia::Factorize(lcm));
vector<i64> cnt(divs.numDivisors());
rep(i,cnt.size()) cnt[i] = lcm / divs.divisor(i);
divs.RevMobius(cnt);
Modint ans = 0;
rep(i,cnt.size()){
Modint tmp = cnt[i];
i64 div = divs.divisor(i);
for(i64 a : A) tmp *= Modint(M).pow(nachia::Gcd(div, a));
ans += tmp;
}
ans /= lcm;
cout << ans.val() << endl;
return 0;
}
struct ios_do_not_sync{
ios_do_not_sync(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
} ios_do_not_sync_instance;