PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Soumyadeep Pal
Tester: Manan Grover, Tejas Pandey
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy-Medium
PREREQUISITES:
PROBLEM:
You are given an integer sequence A=(A_1, A_2,\dots, A_N) of length N and an integer M such that 0 \leq M \lt \sum\limits_ {i=1}^N A_i.
An integer sequence B=(B_1, B_2,\dots, B_N) of length N is called good if:
- 0 \le B_i \le A_i for each 1\le i \le N
- B_1+ B_2+\dots+B_N=M
Find the maximum value of \gcd(A_1-B_1,A_2-B_2,\dots,A_N-B_N) over all good sequences B. Here, \gcd denotes the greatest common divisor.
Note: \gcd(a,b,c) = \gcd(a,\gcd(b,c)) and \gcd(a,0)=\gcd(0,a)=a.
EXPLANATION:
Subtask 1
Observation
Let d be the GCD of numbers X and Y, then d is a factor of (X+Y).
Proof: Given d as the GCD of X and Y. This means that we can write X = d \cdot X' and Y = d \cdot Y'. Now, X+Y = d \cdot X' + d \cdot Y' = d \cdot (X'+Y').
Thus, d is a factor of X+Y.
We can extend this observation for a sequence of numbers.
In the problem, assume d as gcd(A_1-B_1, A_2-B_2, …, A_N-B_N).
This means that d must be a factor of \sum_{i=1}^{N}(A_i-B_i).
Also, \sum_{i=1}^{N}(A_i-B_i) = \sum_{i=1}^{N}(A_i) - \sum_{i=1}^{N}(B_i) = \sum_{i=1}^{N}(A_i) - M.
This means that d must be a factor of \sum_{i=1}^{N}(A_i) - M.
Traverse through all factors of \sum_{i=1}^{N}(A_i) - M and check if it can be a possible answer. The maximum value among all possible GCDs is the answer.
How to check if X can be equal to gcd(A_1-B_1, A_2-B_2, …, A_N-B_N)?
For X to be gcd(A_1-B_1, A_2-B_2, …, A_N-B_N), for all (1 \leq i \leq N) one of the following should satify:
- (A_i-B_i) = 0, or
- (A_i - B_i) is a multiple of X.
To make A_i a multiple of X, we need to subtract A_i - X \cdot \frac{A_i}{X} from it. This way we reduce A_i to the greatest integer divisible by X but less than equal to A_i. Therefore, if we take B_i = A_i - X \cdot \frac{A_i}{X} or equivalently B_i = A_i \%X, we ensure that gcd(A_1-B_1, A_2-B_2, …, A_N-B_N) is X and \sum_{i = 1}^{N}B_i is the minimum value that satisfies this condition.
Let S = \sum_{i = 1}^{N}B_i = \sum_{i = 1}^{N}(A_i\%X). We are given that \sum_{i = 1}^{N}B_i should be equal to M. Three cases are possible:
- Case S = M: All of the conditions are satisfied and thus, X can be a possible answer.
- Case S > M: Since S is the minimum sum for which X is the gcd. If S>M, we cannot choose X as one of the possible answers.
-
Case S < M: We know that \sum_{i=1}^{N}(A_i) - M is a multiple of X. Thus,
(\sum_{i=1}^{N}(A_i) - M) \% X = 0. This means that (M - (\sum_{i=1}^{N}A_i ) \% X) \% X = 0 or (M - S)\%X = 0.
Now since (M-S) is a multiple of X, we can add (M-S) to a B_i such that \sum_{i = 1}^{N}B_i becomes M and gcd(A_1-B_1, A_2-B_2, …, A_N-B_N) remains X.
To sum up, if S \leq M, X can be a possible answer. Our final answer is the maximum out of all such possible answers.
Complexity
Let D denote the number of factors of \sum_{i=1}^{N}(A_i) - M. The complexity of this approach would be O(D \cdot N) as for each factor, we check in O(N) if it can be a possible answer or not.
Subtask 2
The possible answer lies in the range [1, 10^5]. Let us check if X can be a possible answer.
To make an element A_i a multiple of X, we need to subtract A_i - X \cdot \frac{A_i}{X} from it. Instead of doing this for each A_i (which runs in O(N)), we use a different approach.
Note that all the elements A_i that lie in the range [0, X-1] would be reduced to 0. For all elements lying in this range, B_i = A_i. Thus, the minimum sum of B_i for making all elements in this range a multiple of X would be \sum A_i.
Similarly, for elements in the range [X, 2 \cdot X - 1], all elements would be reduced to X (the greatest multiple less than equal to that the element) and thus, B_i = A_i - X. For this range, the minimum sum of B_i required to make all elements in this range a multiple of X would be \sum B_i = \sum A_i - cnt \cdot X, where cnt is the count of elements in range [X, 2 \cdot X - 1].
For elements in the range [p \cdot X, (p+1) \cdot X - 1], all elements would be reduced to p \cdot X and thus, B_i = A_i - p \cdot X. For this range, \sum B_i = \sum A_i - cnt \cdot (p \cdot X).
Note that if we have the sum of elements and count of elements in a range, we can calculate \sum B_i for the range in constant time. Thus, we should precalculate both the sum and count of elements.
Let S be the sum of \sum B_i over all such possible ranges. This means that S is the minimum value of \sum_{i=1}^{N}B_i for which we can make gcd(A_1-B_1, A_2-B_2, …, A_N-B_N) equal to X.
X can be a possible gcd only if S \leq M and (M-S)\%X=0.
Conclusion: For each 1 \leq i \leq 10^5, we calculate the sum of elements till i and the count of elements till i.
Iterate over all values X,(1 \leq X \leq 10^5) and check if it can be a possible answer for gcd in O(\frac{N}{X}) time. The final answer is the maximum out of all possible answers.
The complexity of this approach would be O(Nlog(N)).
TIME COMPLEXITY:
The time complexity is O(Nlog(N)) per test case.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 1;
int n, m, sum[N], cnt[N];
void solve(int tc) {
cin >> n >> m;
for (int i = 0; i < N; i++) {
cnt[i] = sum[i] = 0;
}
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
sum[x] += x;
}
for (int i = 0; i < N - 1; i++) {
cnt[i + 1] += cnt[i];
sum[i + 1] += sum[i];
}
int ans = 1;
for (int i = 2; i < N; i++) {
int total = 0, num = 0;
for (int j = 0; j < N; j += i) {
int cur_sum = sum[min(N - 1, j + i - 1)] - (j ? sum[j - 1] : 0LL);
// sum of numbers in the range [j, j + i - 1]
int cur_cnt = cnt[min(N - 1, j + i - 1)] - (j ? cnt[j - 1] : 0LL);
// count of numbers in the range [j, j + i - 1]
total += (cur_sum - cur_cnt * j);
// minuimum what we have to subtract to make gcd i
}
if (total <= m && (m - total) % i == 0) {
ans = i;
}
}
cout << ans << '\n';
}
int32_t main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) solve(i);
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
long long cnt[MAX_N + 1], sum[MAX_N + 1];
long long gsum(int l, int r) {
return sum[r] - sum[l];
}
long long gcnt(int l, int r) {
return cnt[r] - cnt[l];
}
int main() {
int t;
cin >> t;
while(t--) {
int n; cin >> n;
long long m; cin >> m;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(cnt));
for(int i = 0; i < n; i++) cnt[a[i]]++, sum[a[i]] += a[i];
for(int i = 1; i <= MAX_N; i++) cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
int res = 1;
for(int i = MAX_N; i > 1; i--) {
long long req = 0;
for(int j = 0; j < MAX_N; j += i) {
long long csum = gsum(j, min(MAX_N, j + i - 1));
long long ccnt = gcnt(j, min(MAX_N, j + i - 1));
req += csum - ccnt*j;
}
if(m - req > -1 && (m - req)%i == 0) {
res = i;
break;
}
}
cout << res << "\n";
}
return 0;
}
Editorialist's Solution (Subtask 1)
#include <iostream>
using namespace std;
int calc(int a[], int n, int hcf){
int total = 0;
for(int i = 0; i<n; i++){
total += a[i]%hcf;
}
return total;
}
int main() {
int t;
cin>>t;
while(t--){
int n, m;
cin>>n>>m;
int a[n];
int sum = 0;
for(int i = 0; i<n; i++){
cin>>a[i];
sum += a[i];
}
int ans = 0;
int diff = sum - m;
for(int i = 1; i*i <= diff; i++){
if(diff%i==0){
int x = i;
int y = diff/i;
int req1 = calc(a, n, x);
if(req1 <= m) ans = max(ans, x);
int req2 = calc(a, n, y);
if(req2 <= m) ans = max(ans, y);
}
}
cout<<ans<<endl;
}
return 0;
}