P10171

Retired_lvmao · 2024-02-18 14:58:00 · 题解

题解

提供一个很可能是乱搞的做法。

首先，先判掉存在两个 A_i 相等的情况，这种情况下答案显然是 0 。接下来，我们默认 A_i 单调递增。

再此基础上，可以注意到 >\max A_i 的 k 都一定合法，接下来我们可以认为 R\leq \max A_i 。

观察到一个 k 合法的充要条件是，不存在一对数 (i,j) ，满足 k 是 A_j-A_i 的因子。然而，暴力 check 的复杂度是 O(n^2+R\log R) 的，不能通过。

又注意到，根据抽屉原理，合法的 k 一定 \geq n 。这提醒了我们，在前一个算法中，只需要考虑 A_j-A_i>n 的数，就可以判定所有的数合不合法。这样做可以预见的会快很多，但是时间复杂度未知，而且足以通过目前的数据。

代码

#include<bits/stdc++.h>
using namespace std;
int n,l,r;
int a[200010];
int vis[400010];
int maxn=4e5;
int main()
{
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=2;i<=n;i++)
        if(a[i]==a[i-1])
        {
            puts("0");
            return 0;
        }
    for(int i=1;i<n;i++)
    {
        int pos=lower_bound(a+1,a+n+1,a[i]+n)-a;
        for(int j=pos;j<=n;j++)
            vis[a[j]-a[i]]=1;
    }
    int sum=max(r-maxn,0);
    for(int i=1;i<=maxn;i++)
    {
        for(int j=i+i;j<=maxn;j+=i)
            vis[i]|=vis[j];
    //  if(vis[i])
    //      cout<<i<<endl;
        sum+=(vis[i]==0&&i>=l&&i<=r&&i>n);
    }
    printf("%d\n",sum);
}