题目链接

题意：

Assume that f(0) = 1 and 0^0=1. f(n) = (n)^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的时候特判。

题目链接

题意：给出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)的时候，该式子依然正确，只不过增加了运算复杂度。。。？ 存疑）

题目链接

题意：求一个楼梯数%m的大小。

思路：指数循环节。

需要注意的是，模数只有最外层是m，每往里一层，模数都变成m=phi(m)

所以可以写个dfs或者先预处理出每一层m存一下。

题目链接

题意：给出n个数,q个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+7的答案是多少。

思路：这道题需要一点欧拉函数的知识。

phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。