odd doctor 已更新

Question for the Leader

Time Limit
8s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
50.00%(2/4)
Description:

JRY is the leader of a village. He has n lands, and there are n roads connecting them. There is at most one road connecting two lands and all lands are connected.

Now, JRY wants to divided the n lands into k disjoint sets of equal size, satisfying that one can move between any two lands belonging to the same set passing only through lands frome this set.

Furthermore, he wants to know how many k(1≤k≤n) he can choose.

Input:

There are multiple testcases, the sum of n is less then 10^6.

For each test case, the first line contains one integer n(1≤n≤10^5).

The next line contains n integers, the i-th integer ai means that there is an edge between i and ai. It is guaranteed that the graph doesn't contain self loops and multiple edges.

Output:

For each testcase print a single integer - the number of ways to choose the integer k.

Sample Input:
6
2 3 4 5 6 1
6
2 4 2 3 4 3
Sample Output:
4
3
Hint:

Case 1 : k = 1,2,3,6  Case 2: k = 1,3,6

Source:

2015 Multi-University Training Contest 4


Submit