### PROBLEM LINK:

**GRUBAN** - Gru is Handing Out Bananas

**Author** - guptaishita24

### DIFFICULTY:

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";
}
}
```