Birthday present

Birthday present

题目描述

Bob’s father’s birthday is coming,.Because Bob’s father is a math teacher so that Bob wanted to give him an array of positive intergers a of length n as a gift.His father thinks that an array’s beauty is the greatest common divisor of all its elements. Bob wants to give him as beautiful an array as possible. But the shop has only one array a left. So Bob wants to decrease some numbers in the array(no more than K for each number).Bob can obtain array b from array a if the following conditions hold: bi > 0; 0 ≤ ai - bi ≤ k for all 1 ≤ i ≤ n.Help Bob find the maximum possible beauty of the array he will give to his father .

输入

The first line contains two integers n and k (1 ≤ n ≤ 3·1e5; 1 ≤ k ≤ 1e6). The second line contains n integers ai (1 ≤ ai ≤ 1e6) — array a.

输出

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

样例输入

6 1 3 6 10 12 13 16

样例输出

3 题目大意：Bob's的父亲生日快到了，他想送给他父亲一个数组长度为n的正整数（送数组？？？），他父亲认为数组的美是这个数组的最大公约数，Bob's想送一个最大公约数最大的数组，但是店里只剩下一个数组了，Bob's可以减少数组中的某些数来改变这个数组的最大公约数，减少最多不超过k。

分析：这个数组的最大公约数<=最小值，并且最小是1；那么我们就可以先找到数组的最小值然后用这个最小值挨个和其他数比较如果全都满足 a[i]-a[i]/min*min<=k&&a[i]-a[i]/min*min>=0 (a[i]/min的余数<=k&&a[i]/min的余数>=0)那么我们要找的就是这个min，否则min自减在循环一次，直到min==1；

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF){ int a[300005]={0}; int minn=1000005; for(int i=0;i<n;i++){ scanf("%d",&a[i]); if(a[i]<minn) minn=a[i]; } int flag,t; for(t=minn;t>0;t--){ flag=1; for(int i=0;i<n;i++){ if((a[i]-a[i]/t*t>k)||(a[i]-a[i]/t*t<0)){ flag=0; break; } } if(flag){ printf("%d\n",t); break; } } } return 0; }