P10704
_Yonder_
·
·
题解
写了一个很奇怪的做法，跑的倒是很快。
我们令 B 为分治界，然后我们要提前求出 a_i\le B 的 \displaystyle\sum_{j = 1}^{n}\left \lfloor \frac{m}{a_ia_j} \right \rfloor，这里只需整除分块加差分即可。
时间复杂度 $O(n\sqrt B+\frac{m}{B})$，会发现 $B$ 取 $10^5$ 时最优（这个做法不需要 $\displaystyle\sum_{i= 1}^{n} a_i\le10^9$ 的条件，而且跑的非常快）。
# Code
```
#include<bits/stdc++.h>
#ifdef ONLINE_JUDGE
static char buf[4500000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,4500000,stdin),p1==p2)?EOF:*p1++
#endif
#define S std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,l,r) for(register int i=l;i<=r;i++)
#define per(i,l,r) for(register int i=l;i>=r;i--)
#define ll long long
#define lt __int128
using namespace std;
template<typename P>inline void read(P&x){bool f=0;x=0;char c=getchar();while(!isdigit(c)) f|=c=='-',c=getchar();while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();x=f?~(x-1):x;}
template<typename P>inline void write(P x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar((x%10)^48);}
//template<typename P>inline void wu(P x){}
#define int long long
const int N=1e6+5,M=5e3+5,mod=998244353;const long long inf=1e17;
int n,m,a[N],last,ans,len,v[N],cnt[N],c[N],b=1e5;
signed main(){
read(n),read(m);rep(i,1,n) read(a[i]);sort(a+1,a+1+n);
per(i,n,1)
if(v[len]==m/a[i]) cnt[len]++;
else v[++len]=m/a[i],cnt[len]=cnt[len-1]+1;
rep(i,1,len){
for(register int l=1,r=0;l<=min(b,v[i]);l=r+1){//数论分块
register int o=v[i]/l;
r=v[i]/o,r=min(r,b);o%=mod;
c[l]+=o*(cnt[i]-cnt[i-1]),c[r+1]-=o*(cnt[i]-cnt[i-1]);//差分
c[l]%=mod,c[r+1]%=mod;
}
}rep(i,1,b) c[i]=((c[i]+c[i-1])%mod+mod)%mod;//忘记+mod调半天
v[++len]=1e16;//边界
rep(i,1,n){
if(a[i]==a[i-1]){ans=(ans+last)%mod;continue;}last=0;
if(a[i]<=b){last=c[a[i]];ans=(ans+last)%mod;continue;}//分治
for(register int j=a[i];j<=m;j+=a[i]){
int l=lower_bound(v+1,v+1+len,j)-v;
if(l==len) break;//边界
int r=lower_bound(v+1,v+1+len,j+a[i])-v;
if(v[r]>=(j+a[i])){
if(l==r){//对于搜不到时的小优化
j=v[r]/a[i]*a[i]-a[i];//for循环时会加上ai，所以提前减去ai
continue;
}
r--;
}
last=((j/a[i])*1ll*(cnt[r]-cnt[l-1])%mod+last)%mod;
if(r+1==len) break;
j=v[r+1]/a[i]*a[i]-a[i];//小优化
}ans=(ans+last)%mod;
}write(ans);
return 0;
}
```