提示: 欢迎访问OurACM平台。
Problem 2031 计数问题

Accept: 36    Submit: 294
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

一个函数f(x) = x^x ,表示x自乘x次之后的结果。例如 f(5) = 5^5 = 3125, f(2) = 2^2 = 4…现在我们定义一个mod操作,表示求模操作。例如 10 mod 3 = 1, 10 mod 7 = 3。(在 C/C++中,mod 操作符为 %, 在Pascal中为mod)。 现在有 g(x,y) = f(x) + f(y) = 0(mod p). 要求找到所有的数对(x,y),满足 (1)1 <= x<= y < p (2)g(x,y) = 0 (mod p) 例如: p = 5, 那么数对 (1,2)是一个解,现在你只需要输出这些数对的个数! 注意: a = b(mod c)实际上是 (a mod c) = (b mod c), 例如 10 = 17(mod 7) 实际上就是(10 mod 7) = (17 mod 7) = 3。

Input

第一行输入一个整数t(t<=100),代表t组测试数据。接下来有t行,每行一组测试数据,每组测试数据输入一个正整数p(2<=p<=10^6,p是一个素数)。

Output

每组测试数据输出一个整数占一行,为所求的数对的个数。

Sample Input

4 2 3 5 7

Sample Output

1 0 2 4

Source

福州大学第八届程序设计竞赛

Submit  Back  Status  Discuss