Chef and easy problem 2
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Roma gave Chef an array of intergers.
Chef wants to make all integers in the array equal to 1.
In a single operation, he can select a prime number p and a subset of the integers, and then divide all of the integers in the subset by p.
Chef can make this operation only if every integer in the selected subset is divisible by p.
Please help Chef to make all the integers in the array equal to 1 with minimum number of operations.
The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the length of the array that Roma gave Chef.
The second line contains N space-separated integers A1, A2, ..., AN denoting the integers in the array.
For each test case, output a single line containing one integer - the minimum number of operations needed to make all numbers equal to 1.
- Subtask 1 (10 points): T = 5, 1 ≤ N ≤ 105, 1 ≤ Ai ≤ 3
- Subtask 2 (40 points): T = 3, 1 ≤ N ≤ 10, 1 ≤ Ai ≤ 106
- Subtask 3 (50 points): T = 3, 1 ≤ N ≤ 105, 1 ≤ Ai ≤ 106
Input: 1 3 1 2 4 Output: 2
|Tags||furko, ltime16, maths, simple|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.