Vasya and Beautiful Arrays CodeForces - 354C (数论，枚举)

Vasya and Beautiful Arrays

Vasya's got a birthday coming up and his mom decided to give him an array of positive integers a of length n.

Vasya thinks that an array's beauty is the greatest common divisor of all its elements. His mom, of course, wants to give him as beautiful an array as possible (with largest possible beauty). Unfortunately, the shop has only one array a left. On the plus side, the seller said that he could decrease some numbers in the array (no more than by k for each number).

The seller can obtain array b from array a if the following conditions hold: b**i > 0; 0 ≤ a**i - b**i ≤ k for all 1 ≤ i ≤ n.

Help mom find the maximum possible beauty of the array she will give to Vasya (that seller can obtain).

Input

The first line contains two integers n and k (1 ≤ n ≤ 3·105; 1 ≤ k ≤ 106). The second line contains n integers a**i (1 ≤ a**i ≤ 106) — array a.

Output

In the single line print a single number — the maximum possible beauty of the resulting array.

Examples

Input

6 13 6 10 12 13 16

Output

Input

5 38 21 52 15 77

Output

Note

In the first sample we can obtain the array:

3 6 9 12 12 15

In the second sample we can obtain the next array:

7 21 49 14 77

题意：

给你一个含有n个数的数组，和一个整数k。

对于数组中的每一个数\(a[i]\), 可以减去\([0,k]\) 。问你修改之后数组的最大公约数是多少？

思路:

首先确定答案的上下界限。

设mn 是数组a中的最小数。

设mx是数组a中的最大值。

显然答案的最大值是mn

再考虑下，如果mn>=k+1 ，

那么答案的最小值是k+1 ,因为将a[i] 对k+1 取模，剩余的每一个a[i]<=k，那么都可以将大于0的a[i]，减为0，即gcd为k+1.

所以现在确定的上下届为\([k+1,mn]\)

那么我们不妨枚举gcd，

从mn 枚举到k+1。

那么这个过程是\(O(n)\)的

对于当前枚举到的gcd为x，如何判断可以修正数组使gcd为x呢？

我们看下只有当一个数\(a[i]\) 在这个区间\([i*x,i*x+k]\)中才可以变为x的倍数。

如果每一个数都在这个区间，那么整个数组就可以修改为每一个a[i] 都是 x的倍数。

那么我们不妨枚举x的倍数i，利用前缀和在\(O(1)\) 时间内获得区间中有多少个数，

最后看总个数是否为N，就可以判断x是否满足条件了。

枚举x的倍数时间复杂度为\(O(log_x(mx))\)

总时间复杂度是\(O(n*logn)\) 可以通过。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define sz(a) int(a.size())

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))

#define du2(a,b) scanf("%d %d",&(a),&(b))

#define du1(a) scanf("%d",&(a));

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}

void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline void getInt(int* p);

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

int n;

int k;

int vis[maxn];

int sum[maxn];

int a[maxn];

int mn = inf;

int mx = -1;

bool check(int x)

{

    int cnt = 0;

    for (int i = 1; i * x <= mx; i++)

    {

        cnt += sum[min(i * x + k, mx)] - sum[i * x - 1];

    }

    return cnt == n;

}

int main()

{

    //freopen("D:\\code\\text\\input.txt","r",stdin);

    //freopen("D:\\code\\text\\output.txt","w",stdout);

    gbtb;

    cin >> n >> k;

    repd(i, 1, n)

    {

        cin >> a[i];

        vis[a[i]]++;

        mn = min(mn, a[i]);

        mx = max(mx, a[i]);

    }

    repd(i, 1, mx)

    {

        sum[i] = sum[i - 1] + vis[i];

    }

    // [ k+1 , mn ]

    //

    if (mn <= k + 1)

    {

        cout << mn << endl;

    }

    else

    {

        for (int i = mn; i >= k + 1; i--)

        {

            if (check(i))

            {

                cout << i << endl;

                break;

            }

        }

    }

    return 0;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西

Vasya and Beautiful Arrays CodeForces - 354C (数论，枚举)

Vasya and Beautiful Arrays

题意：

思路:

细节见代码：

最新文章

热门文章