题解：P10704 救赎（Redemption）

· · 题解

题意简明，不再赘述。

分析

简单的套路题，首先有 \lfloor \frac{m}{a_i a_j} \rfloor = \lfloor \frac{\lfloor \frac{m}{a_i} \rfloor}{a_j} \rfloor ，发现枚举 a_i 时，分子为定值，考虑简化。所以定义一个函数 f(x) = \sum\limits_{i=1}^{n} \lfloor \frac{x}{a_i} \rfloor ，那么所求答案变为 \sum\limits _{i=1}^{n} f(\lfloor \frac{m}{a_i} \rfloor) 。

看到取整自然想到整除分块，这题就变成了整除分块套整除分块。与常规的整除分块不同， a_i 所对应的自然数并不连续。考虑将 a 数组排序，当我们处理到 a_i 时，二分查找最靠右的 a_j ，使得 \lfloor \frac{m}{a_i} \rfloor = \lfloor \frac{m}{a_j} \rfloor （这一步实际上是查找整除分块的块右端点），之后计算一次 f(\lfloor \frac{m}{a_i} \rfloor) ，再乘上区间长度，就是当前块的答案，然后将 i 挪到 j+1 。

额，可能有点突然，我比赛时就是这样过了，严谨时间复杂度不会算，但显然一定是在 O(n) 到 O(m) 范围内的，且远远跑不到 O(m) 。

代码

没有刻意压行，代码和思路有略微差别，差别在于代码里二分的是块右端点右一个的位置。

#include <iostream>
#include <algorithm>
#define int ll
using namespace std;
using ll= long long;
const int N=1e6+5,mod=998244353;
ll n,m,a[N],ans;
char buf[1<<20],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int read(){
    int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return x;
}
inline ll f(ll x){ ll ret=0;
    for(int i=1,j=1;i<=n;i=j){
        if(a[i]>x) break;
        j=upper_bound(a+1,a+1+n,x/(x/a[i]))-a;
        (ret+=(ll)(j-i)*(x/a[i])%mod)%=mod;
    } return ret;
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+1+n);
    for(int i=1,j=1;i<=n;i=j){
        if(a[i]>m) break;
        j=upper_bound(a+1,a+1+n,m/(m/a[i]))-a;
        (ans+=(j-i)*f(m/a[i])%mod)%=mod;
    } return !printf("%lld",ans);
}