Chef and Round Run
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef cooks nice receipes in the cafeteria of his company. The cafe contains N boxes with food enumerated from 1 to N and are placed in a circle in clocwise order (boxes 1 and N are adjacent). Each box has unlimited amount of food with a tastyness level of Ai. Chef invented a definition of a magic box!
- Chef picks a box i and stays in front of it.
- Now Chef eats food from box i and skips next Ai boxes.
- Now Chef is staying at some other (probably even the same!) box and repeats.
- Box i is a magic box if at some point of such game started from box i, Chef will find himself staying in front of it again.
When Chef came home, Chef's dog Tommy asked him about how many magic boxes were in the cafe? Help Chef to in finding that!
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 boxes.
The second line contains N space-separated integers A1, A2, ..., AN denoting the tastyness levels of each box.
For each test case, output a single line containing number of magical boxes.
- 1 ≤ sum of all N over all the test cases in a single test file ≤ 106
- 0 ≤ Ai ≤ 109
- Subtask #1 (30 points): 1 ≤ sum of all N over all the test cases ≤ 104; 1 ≤ N ≤ 1000
- Subtask #2 (70 points): 1 ≤ sum of all N over all the test cases ≤ 106; 1 ≤ N ≤ 105
Input: 3 4 1 1 1 1 4 3 0 0 0 4 0 0 0 2 Output: 4 1 2
Example case 1.Here are Chef's paths if he starting from each the box:
1->3->1 2->4->2 3->1->3 4->2->4As you see, all 4 boxes are magical.
Example case 2.Here are Chef's paths if he starts from each box appropriately:
1->1 2->3->4->1->1 3->4->1->1 4->1->1AS you see, only box 1 is magical.
|Tags||aug16, berezin, graph, simple|
|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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.