No.811 Maximizing the Number of Divisors
Shuz*
tatyamProblem Statement
Write a program that, among the natural numbers smaller than a composite number $N$ that have at least $K$ prime factors in common with $N$, outputs the natural number $M$ with the most divisors. If there are multiple such $M$, output the smallest $M$.
Here, when counting prime factors, the same prime factor occurring multiple times is counted separately.
Example: The common prime factors of $4$ and $8$ are $\{2, 2\}$, and their count is $2$.
Note: A natural number having the most divisors among the natural numbers up to a certain number is called a highly composite number. Be careful, as this problem does not ask for a highly composite number not exceeding $N$.
Input
$N\ K$
The first line contains a composite number $N$ and a natural number $K$, separated by a space.
Output
Among the natural numbers smaller than $N$ that have at least $K$ of the prime factors of $N$, output the smallest $M$ among those with the maximum number of divisors.
Constraints
$4 \le N \le 100000$
$1 \le K \le 15$
$K <$ (the number of prime factors of $N$)
Sample
Sample 1
Input
48 4
Output
24
$48=2\times2\times2\times2\times3$, and $M$ has $4$ of these prime factors, so $M$ has $2\times2\times2\times2=16$ or $2\times2\times2\times3=24$ as a divisor. Among such natural numbers smaller than $N$, the one with the maximum number of divisors is $M=24$, whose divisors are the $8$ numbers $1,2,3,4,6,8,12,24$. Since this is the maximum, output 24.
Sample 2
Input
1000 1
Output
840
Sample 3
Input
90720 9
Output
75600
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。