Little Chef and Cake
All submissions for this problem are available.
Little Chef doesn't like repeated things. He calls a number n Good if there are no repeating prime factors in its prime decomposition. Little Chef has just won the best chef award. There is a huge cake with N pieces arranged in a single row. Each piece of cake was made by a different chef; so each piece i has a score Ai associated with it. The score of multiple pieces of cake is the product of the scores of the individual pieces. As prize for winning the best chef award, Little Chef can choose any contiguous part of the cake and eat it. In how many ways can little chef choose this part such that the score of that part is Good?
- The first line of the input contains an 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 number of pieces in the cake. The second line contains N space-separated integers A1, A2, ..., AN denoting the score of each piece.
- For each test case, output a single line containing the number of ways chef can choose a contiguous part of the cake such that the score is good.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 1000
- Sum of N over all test cases does not exceed 5x105
SubtasksSubtask #1 (10 points)
- 1 ≤ N ≤ 100
- Score of entire cake will not exceed 1018
- Ai = 1
- 1 ≤ Ai ≤ 2
- Original constraints
Input: 5 2 1 1 4 2 1 1 2 8 11 3 1 3 7 7 11 1 1 144 11 2 1 5 8 12 6 100 14 49 42 65 Output: 3 9 17 0 11
Example case 1. There are 2 pieces each with score 1. Chef can choose either one of the pieces by itself or the whole cake and all of them will have score 1, which is good
Example case 2. There are total 10 ways to choose a contiguous section of the cake. Of them only 1 way is bad - choosing the whole cake gives a score of 2x1x1x2 = 4 which has 2 as a repeating prime factor
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions