题解：P10704 救赎（Redemption）

· · 题解

题目传送门。

思路

容易得到 \lfloor\frac{m}{i}\rfloor 只有 2\sqrt m 种取值，考虑对 m 数论分块，对于每个区间 \forall i,j\in[l,r]，均有 \lfloor\frac{m}{i}\rfloor=\lfloor\frac{m}{j}\rfloor，令 f(r)=\sum_{i=1}^n \sum_{j=1}^n [a_ia_j\le r]，b_i=\sum_{j=1}^n [a_j=i]，那么我们有

f(r)=2\sum_{i=1}^{\lfloor\sqrt{r}\rfloor} b_i\left( \sum_{j=1}^n [a_j\le \lfloor\frac{r}{i}\rfloor]-\sum_{j=1}^n [a_j\le i] \right)+\sum_{i=1}^{\lfloor\sqrt{r}\rfloor} b_i^2

由于传入函数 f 的参数均是 m 的整除点值，而 m 的整除点值只有 2\sqrt m 种，括号内的式子我们就可以在 O(\sqrt m\log n) 的时间复杂度内求出。

那么 f(r) 就能在 O(\sqrt r) 的时间复杂度内求出。

最终答案就是：

\sum_{l,r}(f(r)-f(l-1))\times \biggl\lfloor\dfrac{m}{l}\biggl\rfloor

时间复杂度 O(m^{3/4}+\sqrt m\log n)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e6+7;
const int Mod=998244353;
ll n,m;
ll a[Maxn]; 
ll sq;
ll ans;
ll sq1[Maxn],sq2[Maxn];
ll bb[Maxn];

inline ll Gt(ll x){
    if(x==0) return 0;
    if(x<=sq) return sq1[x];
    else return sq2[m/x];
}
map<ll,ll>S;
inline ll KP(ll x){
    if(S.count(x)) return S[x];
    ll res=0;

    ll pp=__builtin_sqrt(x);
    for(ll i=1;i<=pp;i++)
        res=(res+bb[i]*(Gt(x/i)-Gt(i)))%Mod;
    res=res*2%Mod;
    for(ll i=1;i<=pp;i++) res=(res+bb[i]*bb[i])%Mod;
    return S[x]=res;
}

int main(){
    scanf("%lld%lld",&n,&m);
    sq=sqrt(m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(a[i]<=sq) bb[a[i]]++;
    }
    sort(a+1,a+n+1);

    for(ll l=1,r;l<=m;l=r+1){
        r=m/(m/l);
        int res=upper_bound(a+1,a+n+1,r)-a-1;
        if(r<=sq) sq1[r]=res;
        else sq2[m/r]=res;
    }
    for(ll l=1,r;l<=m;l=r+1){
        r=m/(m/l);
        ans=(ans+(KP(r)-KP(l-1))%Mod*(m/l)%Mod)%Mod;
    }
    ans=(ans+Mod)%Mod;
    printf("%lld",ans);

    return 0;
}