链接:
http://exam.upc.edu.cn/problem.php?id=4198
题目：
题目描述
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
题意：
给你n个数和一个k，你可以将n个数里的任意个数减去1~k，问你这个序列最大公共gcd。
思路：
暴力枚举最小的数a到a-k的所有因子，然后
O(n)
扫，如果对于当前数
num[i]
，有
num[i]%a<=k
，那么说明这个数通过一定操作是可以拥有a这个因子的。
实现：
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <list>
#include <iomanip>
#include <functional>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#define edl putchar('\n')
#define ll long long
#define clr(a,b) memset(a,b,sizeof a)
#define rep(i,m,n) for(int i=m ; i<=n ; i++)
#define fep(i,n) for(int i=0 ; i<n ; i++)
namespace FastIO {
const int SIZE =
1 <<
16;
char buf[SIZE], obuf[SIZE], str[
60];
int bi = SIZE, bn = SIZE, opt;
int read(
char *s) {
while (bn) {
for (; bi < bn && buf[bi] <=
' '; bi++);
if (bi < bn)
break;
bn = fread(buf,
1, SIZE, stdin);
bi =
0;
}
int sn =
0;
while (bn) {
for (; bi < bn && buf[bi] >
' '; bi++) s[sn++] = buf[bi];
if (bi < bn)
break;
bn = fread(buf,
1, SIZE, stdin);
bi =
0;
}
s[sn] =
0;
return sn;
}
bool read(
int& x) {
int n = read(str), bf;
if (!n)
return 0;
int i =
0;
if (str[i] ==
'-') bf = -
1, i++;
else bf =
1;
for (x =
0; i < n; i++) x = x *
10 + str[i] -
'0';
if (bf <
0) x = -x;
return 1;
}
};
#define read(x) FastIO::read(x)
using namespace std;
const int maxn =
int(
3e5)+
7, INF =
0x3f3f3f3f;
int num[maxn], n, k, minn;
set<int, greater<int> > st;
int main() {
#ifndef ONLINE_JUDGE
freopen(
"../in.txt",
"r", stdin);
printf(
"init! init! init!\n");
#endif
while(minn = INF, st.clear(), read(n), read(k)) {
fep(i,n) read(num[i]), minn = min(minn, num[i]);
for(
int j=minn ; j>=minn-k ; j--)
for(
int i=
1 ; i*i<=j ; i++)
if(!(j%i)) st.insert(i), st.insert(j/i);
auto it = st.begin();
for( ; it != st.end() ; it++) {
bool flag =
true;
fep(i,n)
if(num[i]%(*it)>k) flag =
false;
if(flag)
break;
}
printf(
"%d\n",*it);
}
return 0;
}
