对 a 离散化(最后只有 O(V) 个值),然后暴力 O(n2) 算,复杂度 O(V)。
感觉可能可以卡过去,毕竟 4s 啊, 4s 啊,4s 啊!!!!!
#include<bits/stdc++.h>
#define ri register int
#define ll unsigned long long
using namespace std;
const int maxn=1e6+7;
const int mod=998244353;
int n;
int a[maxn];
int lsh[maxn];
int tot;
int tong[maxn];
namespace IO {
int len = 0;
char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
#define gh() \
(iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1,stdin), \
(iS == iT ? EOF : *iS++) : *iS++)
inline ll read() {
char ch = gh();
ll x = 0;
char t = 0;
while (ch < '0' || ch > '9')
t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ 48), ch = gh();
return t ? -x : x;
}
inline void putc(char ch) {
out[len++] = ch;
}
template <class T> inline void write(T x) {
if (x < 0)
putc('-'), x = -x;
if (x > 9)
write(x / 10);
out[len++] = x % 10 + 48;
}
template < > inline void write<const char*> (const char* x) {
int i=0;
while(x[i]!='\0') out[len++] = x[i++];
}
template < > inline void write<char*> (char* x) {
int i=0;
while(x[i]!='\0') out[len++] = x[i++];
}
template <class T> inline void write(T x,char a){
write(x);
out[len++] = a;
}
inline void flush() {
fwrite(out, 1, len, stdout);
len = 0;
}
}
using IO::flush;
using IO::putc;
using IO::read;
using IO::write;
ll llsh[maxn];
int ttot;
ll b[maxn];
int ttong[maxn];
signed main(){
ios::sync_with_stdio(0);
ll m;
n=read();m=read();
for(ri i=1;i<=n;i++){
a[i]=read();
lsh[i]=a[i];
}
sort(lsh+1,lsh+1+n);
tot=unique(lsh+1,lsh+1+n)-lsh-1;
for(ri i=1;i<=n;i++){
a[i]=lower_bound(lsh+1,lsh+1+tot,a[i])-lsh;
}
for(ri i=1;i<=n;i++)tong[a[i]]++;
for(ri i=1;i<=tot;i++){
b[i]=m/lsh[i];
llsh[++ttot]=b[i];
}
sort(llsh+1,llsh+1+ttot);
ttot=unique(llsh+1,llsh+1+ttot)-llsh-1;
for(ri i=1;i<=tot;i++){
ttong[lower_bound(llsh+1,llsh+1+ttot,b[i])-llsh]+=tong[i];
}
int ans=0;
for(ri i=1;i<=ttot;i++){
for(ri j=1;j<=tot;j++){
ans=ans+(llsh[i]/lsh[j])*ttong[i]%mod*tong[j]%mod;
if(ans>mod)ans-=mod;
}
}
write(ans);
flush();
return 0;
}