hdu 2837 Calculation (指数循环节+欧拉函数)

题目链接

题意:

Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x).
思路:指数循环节。
trick点在于0^0=1这点。
比较容易想到的一层是ksm的时候特判。
比较不容易想到的一层是,0作为底数的时候,可能出现0^a在用降幂公式加速后,出现0^0。
举个例子:
680 80
phi(80)=32,恰好是8^6的因子
而0^(8^6)答案应该为0,用降幂公式加速后变成了0^0,答案变成了1,结果错误
究其原因,是因为这道题中底数可能有0以及0^0是题目中定义的运算。
解决办法是ksm的结果判断一下,如果是0就加mod。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz