eolymp
bolt
Try our new interface for solving problems
Məsələlər

Maximal Number of Divisors

Maximal Number of Divisors

Zaman məhdudiyyəti 30 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Help Mr. Strange to solve the following problem: "Find the maximum number of positive divisors of all integers in the interval from 1 up to and includingN (1N42^42)". Since it is Mr. Strange who solves the problem, the situation is complicated by the fact that he dislikes number P. Therefore, you should not find the actual maximum number of divisors of all possible numbers from 1 to N, but the maximum number of divisors only for numbers from 1 to N, which are not divisible by P.

Giriş verilənləri

The input file contains several data sets. Your program reads the number of data sets T (2T42), followed by the actual data sets. Each data set contains exactly three lines. The first line contains the number P (which is disliked by Mr. Strange; 2P_{ }1000000007). The second line contains the numberK (1K_{ }42) of intervals [1, N] for which the solution is to be found. The third line contains K space-separated integers, N_i, each in the range 1N_i_{ }42^42 representing the upper limit of each interval.

Çıxış verilənləri

The result for each of the T data sets should be written on separate lines. The results for the intervals [1, N_i] should be space-separated.

Explanation. In each data set you are asked to find the maximal number of divisors for numbers in intervals [1, 8] and [1, 42]. If Mr. Strange dislikes P=13, the maximum number of divisors is 4 and is reached for the numbers 6 (divisors 1, 2, 3 and 6) and 8 (divisors 1, 2, 4 and 8); the maximum number of divisors 9 is reached for the number 36. If Mr. Strange dislikes P=6, numbers 6, 12, 18, 24, 30, 36, 42 are prohibited. So, the same maximum 4 is reached only for the number 8; no number in the interval [1, 42] has 9 divisors, but the maximum number 8 is reached for the number 40.

Nümunə

Giriş verilənləri #1
2
13
2
8 42
6
2
8 42
Çıxış verilənləri #1
4 9
4 8
Mənbə ACM ICPC SEERC-2012, 13.10.2012 Bucharest, Vinnica