T^T Saffah大神照样刷我这样诚心诚意想做一套NOIP模拟题的蒟蒻.

第一题 九九归一

好diao的名字...

题意就是给定一队$n,q$,求在模$n$意义下一个数$x$自乘的循环节长度.

当$x=0$时候输出$0$是吧...

.................................................实在是太弱了....................................................

连个思路都没有.....

再看一遍题目

萌蛋在练习模n意义下的乘法时发现，总有一些数，在自乘若干次以后，会变成1。例如n=7，那么5×5 mod 7=4,4×5 mod 7=6,6×5 mod 7=2,2×5 mod 7=3,3×5 mod 7=1。如果继续乘下去，就会陷入循环当中。萌蛋还发现，这个循环的长度经常会是φ(n)，即小于n且与n互质的正整数的个数。例如，φ(7)=6，而上述循环的长度也是6，因为5,4,6,2,3,1共有6个数。再如n=6，那么5×5 mod 6=1。这个循环的长度很短，只有2，而恰好φ(6)=2。然而，对于某些情况，虽然循环的长度可以是φ(n)，但存在比φ(n)更小的长度：例如n=7，而2×2 mod 7=4,4×2 mod 7=1，循环的长度只有3。当然，6也可以是一个循环的长度。假设已知了n，我们称数a神奇的，当且仅当关于数a的循环长度可以是φ(n)，而且不存在比φ(n)更小长度的循环。例如对于n=7，5是神奇的，而2不是神奇的。现在给出n和q次询问，每次询问给出a，问a是否是神奇的。

 这个循环长度为φ(n)的条件...既然$x^{φ\left( n\right)}\equiv 1 \pmod{n}$,看起来很像欧拉定理...大声告诉我是不是!!!

光知道这个有个P用...真是书到用时方恨少...

还是等Saffah大神的官方题解吧

CH round #55 Streaming #6