CF1789E题解

thostever · 2023-02-27 21:03:58 · 题解

非常有意思的题目。

我们考虑枚举每个 x 算其贡献。

首先我们统计出 s_i 的桶的前缀和，记为 cnt_i。方便计算。

情况 1：

若 x 是 s_n 的因数：

我们直接枚举 \frac{s_n}{x} 的所有倍数，检查是否存在，算答案即可。复杂度是调和级数级别的。

情况 2：

若 x 不是 s_n 的因数：

我们令 k=\left \lfloor \frac{s_n}{x} \right \rfloor ，则有\left \lceil \frac{s_n}{x} \right \rceil =k+1。

由此可知，当 s_i\mod k \leq \left \lfloor \frac{s_i}{k} \right \rfloor 时，存在 p_i 和 q_i 的解。

当 \left \lfloor \frac{s_i}{k} \right \rfloor=j 时，s_i\in [jk,jk+j]。（只需要考虑 j<k 的情况，因为 s_i\geq k^2 时一定存在解）

这样我们就根据 j\in [1,k-1] 把所有的 s_i 划分成 k-1 个区间，每个区间直接算贡献即可。同时也要加上 s_i\geq k^2 的贡献。

对于所有 k\leq \sqrt{s_n}，每次计算 k 个区间，一共计算 k^2 次，总复杂度不超过 O(s_n)。

对于所有 k>\sqrt{s_n}，每次最多有 \left \lfloor \frac{s_n}{k} \right \rfloor \leq \sqrt{s_n} 个区间（k\times j\geq s_n 时无意义）。由于整除分块，最多有 \sqrt{s_n} 个 k，总复杂度不超过 O(s_n)。

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,m;
int s[1000010];
int cnt[10000010];
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&s[i]);
    m=s[n];
    for(int i=1;i<=m;i++) cnt[i]=0;
    for(int i=1;i<=n;i++) cnt[s[i]]++;
    for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
    int ans=0;
    int lst=0;
    for(int i=1;i<=m;i++)
    {
        int sum=0;
        int k=m/i;
        if(m%i==0)
        {
            for(int j=k;j<=m;j+=k) sum+=cnt[j]-cnt[j-1];
        }
        else
        {
            if(m%(i-1)!=0&&int(m/(i-1))==k) sum=lst;
            else
            {
                for(int j=1;j<k&&j*k<=m;j++) sum+=cnt[min(j*k+j,m)]-cnt[j*k-1];
                if(1ll*k*k<=1ll*m) sum+=cnt[m]-cnt[k*k-1];
            }
        }
        ans=(1ll*i*sum+ans)%mod;
        lst=sum;
    }
    printf("%d\n",ans);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}
/*

*/