Codeforces Round 276 (Div. 1) B. Maximum Value（数学+二分）【2100】

题目链接

https://codeforces.com/contest/484/problem/B

思路

$amodb$可以转化成$a-k\times b$，其中$k=\lfloor \frac{a}{b}\rfloor$。

我们发现$k\times b<a<(k+1)\times b$。

我们可以枚举$k$和$b$，在排序去重后的数组中二分查找最大的$a$。

枚举$k$和$b$的时间复杂度为调和级数，最后的时间复杂度为：$O(n(lo{g}_{2}n{)}^2)$

代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

typedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;

const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;

std::mt19937 rnd(time(0));

int n;
int a[N];
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	int maxx = *max_element(a + 1, a + 1 + n);
	int idx = unique(a + 1, a + 1 + n) - a - 1;
	int ans = 0;
	for (int i = 1; i <= idx; i++)
	{
		for (int k = 1; k <= maxx / a[i]; k++)
		{
			int id = lower_bound(a + 1, a + 1 + n, (k + 1) * a[i]) - a;
			id--;
			ans = max(ans, a[id] % a[i]);
		}
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	// cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}