A Balanced Problemset? (Codeforces 1925B)
Tags: Greedy, number theory

Jay managed to create a problem of difficulty $$$x$$$ and decided to make it the second problem for Codeforces Round #921. But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of $$$n$$$ sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to $$$x$$$. The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset. Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.

Input: The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10^3$$$) denoting the number of test cases.Each test case contains a single line of input containing two integers $$$x$$$ ($$$1\leq x\leq 10^8$$$) and $$$n$$$ ($$$1\leq n\leq x$$$).

Output: For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.

Note: For the first test case, one possible way is to break up the problem of difficulty $$$10$$$ into a problemset having three problems of difficulties $$$4$$$, $$$2$$$ and $$$4$$$ respectively, giving a balance equal to $$$2$$$.For the second test case, there is only one way to break up the problem of difficulty $$$5$$$ into a problemset of $$$5$$$ problems with each problem having a difficulty $$$1$$$ giving a balance equal to $$$1$$$.

Sample Inputs:
3
10 3
5 5
420 69

Sample Outputs:
2
1
6

Solution (Python):
import sys

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
maxn = 10 ** 4
bb = [0] * maxn
prime = []
for i in range(2, maxn):
    if bb[i] == 0:
        prime.append(i)
        for j in range(i, maxn, i):
            bb[j] = 1
mod = 998244353
T = int(input())
while T:
    T -= 1
    try:
        (X, N) = [int(i) for i in input().split()]
        d = {}
        X2 = X
        for p in prime:
            while X % p == 0:
                d[p] = d.get(p, 0) + 1
                X = X // p
        if X > 1:
            d[X] = 1
        X = X2
        l = list(d.items())
        ans = 1

        def dfs(index, n):
            if index == len(l):
                if n >= N:
                    global ans
                    ans = max(ans, X // n)
                return
            for i in range(l[index][1] + 1):
                dfs(index + 1, l[index][0] ** i * n)
        dfs(0, 1)
        print(ans)
    except EOFError:
        break

Solution (Python):
import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
    N = 10 ** 5
    prime = [True for i in range(N + 1)]
    p = 2
    while p * p <= N:
        if prime[p] == True:
            for i in range(p * p, N + 1, p):
                prime[i] = False
        p += 1
    arr = []
    for p in range(2, N + 1):
        if prime[p]:
            arr.append(p)
    from collections import defaultdict
    for _ in range(int(input())):
        (x, n) = map(int, input().split())
        p = x
        if x % n == 0:
            print(x // n)
            continue
        fac = []
        i = 0
        while arr[i] * arr[i] <= x:
            while x % arr[i] == 0:
                fac.append(arr[i])
                x = x // arr[i]
            i += 1
        if x > 1:
            fac.append(x)
        global ans
        ans = 1

        def dfs(i, curr):
            global ans
            if i == len(fac):
                if curr >= n:
                    ans = max(ans, p // curr)
                return
            dfs(i + 1, curr * fac[i])
            k = i + 1
            while k < len(fac) and fac[k] == fac[i]:
                k += 1
            dfs(k, curr)
        dfs(0, 1)
        print(ans)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()

Solution (Python):
from bisect import bisect_left

def divisors(n):
    S = set()
    for i in range(1, int(n ** 0.5) + 1):
        if not n % i:
            S.add(i)
            if i ** 2 != n:
                S.add(n // i)
    return sorted(S)
for _ in range(int(input())):
    (x, n) = map(int, input().split())
    D = divisors(x)
    i = bisect_left(D, n)
    print(x // D[i])