 # 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