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