题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4335
题意:给定b,p,m( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 – 1 ),求满足n^(n!)=b(mod p)且0<=n<=m的n有多少个。
理论支撑:
具体证明见:http://blog.csdn.net/longshuai0821/article/details/7826126
解法: n如果很大,n>=phi(p),那么n! mod phi(P) 为0, 于是问题等价为 n^phi(p)=b(mod p)
于是我们可以求得
ni=ci(mod p),由于如果ni是方程的一个解,那么ni+k*p也是方程的解,所以只需要暴力phi(p)--phi(p)+p-1里面的解就可以了
求的方法......
阅读全文