P10704题解 数论分块

· · 题解

思路

第一眼看到这题，想到的就是数论分块。可以参见 P2261。

但显然还是有点不同的，因为这题有两个求和，该怎么办呢？

我稍微思考了一下，发现就是 \left \lfloor \frac{m}{a_ia_j} \right \rfloor 这个东西，可以考虑先将 i，j 分开。它可以是 \left \lfloor \frac{\left \lfloor \frac{m}{a_i} \right \rfloor}{a_j} \right \rfloor，然后对于 j 的求和就是一个标准的数论分块。

但是这里数论分块貌似有点特殊，因为分母不都是连续的，看来只能离散化然后每次二分或者倍增跳，很好很好。

感觉没什么问题，算一下复杂度是 O(n\sqrt{m})，这也过不了啊?

没错这东西肯定是有用的，因为 1 加到 50000 是大于 10^9 的，那么 a_i 的种类数肯定是不超过 50000 的，这样就可以在枚举 i 的时候直接改成枚举 a_i 的值，乘上对应系数即可。

不愧是我。复杂度 O(50000 \times \sqrt{m})，注意到时间限制足足有 4s，加上信仰足矣。开冲！！！

代码

以下为代码参考。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll mod=998244353;
ll n,m,a[N],ans,g[N],c[N],sumc[N],tot;
int main()
{
    scanf("%lld%lld",&n,&m);
    for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    ll cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]!=a[i-1])c[tot]=cnt,g[++tot]=a[i],cnt=1;
        else cnt++;
    }
    c[tot]=cnt;
    for (int i=1;i<=tot+1;i++)sumc[i]=sumc[i-1]+c[i];
    for (int t=1;t<=tot;t++)
    {
        ll k=m/g[t];
        for (int i=g[1],j,pos=1,lpos;i<=1e9 && j<=1e9 && pos<=tot;i=g[pos])
            {
                if (k/i)j=min(k,k/(k/i));
                else j=1e9;
                lpos=pos-1;
                pos=upper_bound(g+1,g+tot+1,j)-g;
                ans+=(k/i)%mod*c[t]%mod*(sumc[pos-1]-sumc[lpos])%mod;
                ans%=mod;
                if (i>g[tot])break;
            }
    }
    printf("%lld",ans);
    return 0;
}

稍微有点丑陋，不管了。