hdu 4335 What is N? (指数循环节+欧拉函数)

题目链接

题意:给出b,p,m(( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 – 1 )),问满足图中条件的n有多少个。

思路:这题由于对p没有限制,所以细节多一些,需要讨论。

首先我们知道指数循环节公式,也就是所谓的降幂公式为:a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c),(ps:后面的限制条件,在x<phi(c)的时候,该式子依然正确,只不过增加了运算复杂度。。。? 存疑)

然后我们只需要对n分两种情况讨论。

第一种是n<t ,第二种是n>=t  (t = min{x| x! % phi(P)==0})

由于t不会很大。。前一种直接暴力。。。

后一种用降幂公式搞之。。。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz