常州模拟赛d5t2 mogician

分析：一个暴力的思想是枚举g,然后枚举每个数ai,看能不能符合要求，这样复杂度是O(nA)的，直接T掉了.也没什么其他的办法了，在暴力的基础上优化一下，优化的关键是要如何快速统计出不满足要求的数的个数.利用数据结构？想不到.仔细分析一下，不满足要求的数组成了很多区间，每次i枚举g的倍数，不满足要求的数的区间总在[i + k + 1,i + g - 1]中，因为i+k+1通过减k满足不了要求，i+g-1比g的倍数少了1，那么利用前缀和数组维护一下个数就好了.不过有一种特殊情况：k >= g - 1,这样无论如何都是满足要求的，因此在前缀和的时候要判断一下左右端点是否合理.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = ;

int sum[maxn], num[maxn],t,n,k,f,mx;

int main()

{

    scanf("%d", &t);

    while (t--)

    {

        memset(sum, , sizeof(sum));

        memset(num, , sizeof(num));

        scanf("%d%d%d", &n, &k, &f);

        for (int i = ; i <= n; i++)

        {

            int t;

            scanf("%d", &t);

            num[t]++;

            mx = max(mx, t);

        }

        for (int i = ; i <= mx; i++)

            sum[i] = sum[i - ] + num[i];

        for (int g = ; g <= mx; g++)

        {

            int cnt = sum[g - ];

            for (int i = g; i + k +  <= mx && cnt <= f; i += g)

            {

                int l = i + k + , r = min(mx, i + g - );

                if (l <= r)

                cnt += sum[r] - sum[l - ];

            }

            if (cnt <= f)

                printf("%d ", g);

        }

        printf("\n");

    }

    return ;

}