囚猪做法

#include<bits/stdc++.h>
#define int long long 
#define cat const auto & 
#define mkp std::make_pair
#define M(x,y) memset(x,y,sizeof(x))
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int & x,int & y){x^=y^=x^=y;}
inline int read()
{
    int x=0,s=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')s=-1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-48;
    return x*s;
}
using PII=std::pair<int,int>;

const int p=998244353;
const int N=10010;

int n,W;
int a[N],b[N];
int ans=0;
int c[N];
int cnt;

std::mt19937 rd(114514);
std::uniform_int_distribution<>bb(1,4e4);
inline void div(int k=W){for(int i=2;k>1;i++)if(k%i==0)while(k%i==0)k/=i,c[++cnt]=i;}

int phi(int x)
{
    int res=1;
    for(int i=2;i*i<=x;i++)
    {
        int k=0;
        while(x%i==0)
        {
            x/=i;
            k++;
        }
        res*=(1+k);
    }
    if(x>1)res<<=1;
    return res;
}

int get()
{
    int sum=1;
    rep(i,1,n)sum=sum*phi(a[i])%p;
    // rep(i,1,n)std::cerr<<a[i]<<'\n';
    return sum;
}

inline void SA()
{
    std::uniform_int_distribution<>aa(1,n);
    double t=1000.0,cg=0.996,et=1e-18,delta;
    int i=1;
    memcpy(a,b,sizeof(a));
    while(t>et)
    {
        if(i>cnt)break;
        int x=aa(rd);a[x]*=c[i];i++;
        int res=get();
        delta=res-ans;
        if(delta>0)ans=res;
        else if(exp(delta/t)<(double)bb(rd)/4e4){a[x]/=c[i-1];i--;}
        t*=cg;
    }
}

void work1()
{
    memcpy(a,b,sizeof(a));
    ans=get();
    printf("%lld\n",(ans%p+p)%p);
}

signed main()
{
    n=read();W=read();div();
    rep(i,1,n)b[i]=read();
    if(W==1){work1();return 0;}
    while((double)clock()/CLOCKS_PER_SEC<=0.9)SA();
    printf("%lld\n",ans);
    return 0;
}