The Codeforces contests are sometimes more challenging than expected, even for the first problems, which are supposed to be trivial. Well, they are not that trivial. In the 762. edition, the 1. problem was concerning the n-th divisor of an integer.
Pretty much, the task looks like this:
You are given two integers n and k. Find k-th smallest divisor of n, or report that it doesn’t exist.
Divisor of n is any such natural number, that n can be divided by it without remainder.
The first line contains two integers n and k (1 ≤ n ≤ 1015, 1 ≤ k ≤ 109).
If n has less than k divisors, output -1.
Otherwise, output the k-th smallest divisor of n.
It looks difficult, and actually it is. The trick is that there is no known algorithm for getting the n-th divisor. But still, we can think of something better than looping up to the end and checking whether the number passes. Thus, looping up to the square root of the number to check is quite enough. The trick is to add also the numbers, which are found through the looping. (This is better to be seen than explained). E.g., if we have 60 and we start looping with 1,2,3,4, etc up to sqrt of 60 when we reach 1, we add 60 as well to the result list, when we are at 2 – we add 30, at 3 we add 20 etc. Then we sort. And pretty much that is it!
Here comes the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class cf1 { static void Main() { string strInfo01 = Console.ReadLine(); long lngNumber = long.Parse(strInfo01.Split()[0]); long lngPosition = long.Parse(strInfo01.Split()[1]); long lngSquare = (long)Math.Sqrt(lngNumber); List<long> lstResults = new List<long>(); for (long i = 1; i <= lngSquare; i++) { if (lngNumber % i == 0) { lstResults.Add(i); if (i != lngNumber/i) { lstResults.Add(lngNumber / i); } } } lstResults.Sort(); if (lstResults.Count< lngPosition) { Console.WriteLine(-1); } else { Console.WriteLine(lstResults [(int)lngPosition-1]); } } } |
Available in GitHub as well.