首先 m = 1 时 ans = 0
对于 m > 1 的 情况
由于 1 到 m-1 中所有和m互质的数字，在 对m的乘法取模 运算上形成了群
ai = ( 1<=a<m && gcd(a,m) == 1 )
所以 对于 a 必然存在b = a^(-1) = inv(a) 使得 a * b = 1 (mod m)
这里存在两种情况
a != b 那么最后的连乘式中a b均出现一次，相乘得1
a == b 那么最后的连乘式中只出现一个a
实际上所有 a = inv(a) 的 ai 连乘就是答案
继续考虑假如 gcd(a,m) == 1 则 gcd(m - a, m) == 1
记m - a = -a (mod m)
那么 a * (-a) = - (a*a) = -1 (mod m)
m != 2时, m - a != a (否则 a = m/2 , gcd(m, m/2) = m/2 != 1)
所以a 和 -a 总是成对出现
所以a^2 = 1 (mod m)的解的个数/2 为奇数时，答案为-1，为偶数时 答案为1
m == 2时，求得答案为1(由于此时1和-1等价，出现了特殊性)
所以对于m > 2的情况，只需求a^2 = 1 (mod m)的解的个数是不是4的倍数
a^2 = 1 (mod m) 等价变换
(a + 1)(a - 1) = 0 (mod m)
假设 m = p0^k0 * p1^k1 * ... * pi^ki (pi为素数)
那么根据中国剩余定理 原方程等价于
方程组 (a + 1)(a - 1) = 0 (mod pi^ki)
先考虑单个方程:
pi > 2 时，(a + 1) 和 (a - 1) 必定有一个和pi互质(否则 pi % 2 == 0)
所以该条方程的解为 ±1 (mod pi^ki)
pi == 2时，
k == 1时 方程解为 1 (mod 2)
k == 2时 方程解为 ±1 (mod 4)
k > 2 方程解为 ±1, (2^(k-1)+1), (2^(k-1)-1) (mod 2^k)
当方程组只有一条方程时，情况如上所示
然后考虑多条方程，合并的情况
根据中国剩余定理，各个式子的各个取值，所有情况在范围内均有且只有一个解
所以方程组解的个数，就是各个方程解的个数的乘积
m > 2时，解的个数不是4的倍数情况（也就是2）只有以下几种
m = 2^2 = 4
m = p^k (p != 2, 且为素数)
m = 2 * p^k (p != 2, 且为素数)
HDU 4910 HDOJ Problem about GCD BestCoder #3 第四题,布布扣,bubuko.com
HDU 4910 HDOJ Problem about GCD BestCoder #3 第四题
原文：http://www.cnblogs.com/hundundm/p/3889927.html