# GRUBAN ENIGMA Editorial

GRUBAN - Gru is Handing Out Bananas
Author - guptaishita24

Easy-Medium

### PREREQUISITES:

GCD, Factorization

### PROBLEM:

Distribute N bananas to K minions in such a way that each minion gets a distinct amount of bananas and gcd of this distribution is highest possible.

### Explanation

Lets assume that the max gcd in g, so the distribution of c_1+c_2 +c_3+...c_k=n can be written as g*( c_1^{\prime} +c_2^{\prime}+....c_k^{\prime})=n where c_i^{\prime} is c_i/g. So now c_1^{\prime} +c_2^{\prime}+....c_k^{\prime}=n/g and all c_i^{\prime} must be distinct so we just assign 1, 2, 3... until possible and give the remaining candies to the last person. Using this formula, we can conclude that the answer is divisor of N which is just greater than \frac{k*(k+1)} 2

### Author solution

Author Solution
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void io(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int N = 1e5 + 5;

int main() {
io();
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
ll kk = 1LL*k*(k+1);
kk/=2;
if(kk>n){
cout<<"-1\n";
continue;
}
vector<ll> v;
for(int i=1;i<=sqrt(n);i++){
if(n%i==0){
v.push_back(i);
if(i != n/i)
v.push_back(n/i);

}

}
sort(v.begin(),v.end());
ll x=lower_bound(v.begin(),v.end(),kk)-v.begin();
cout<<n/v[x]<<"\n";
}
}

3 Likes

i didnt understand this can you pls elaborate

The minimum number of bananas required is T = g*(1+2+...+k) = g*(k*(k+1))/2.

Now, the remaining bananas (N-T) should be a multiple of g for g to be the gcd. We can give the remaining bananas to the guy with highest number of bananas.

So N-T = c*g and N = T + c*g.
So, N = g*(k*(k+1))/2 + c*g

So g is a factor of N. Among all factors, we need the factor greater than (k*(k+1))/2 and then divide N by that factor to get highest possible gcd.

3 Likes

you cleared my doubts thanks!