HDU 4910 HDOJ Problem about GCD BestCoder #3 第四题

首先 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 第四题

最新文章

热门文章