111qqz的小窝

老年咸鱼冲锋!

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。

 

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不会很大。。前一种直接暴力。。。

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

 

 

uva 10692 Huge Mods (欧拉函数,指数循环节)

题目链接

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

思路:指数循环节。

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

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

记得考虑n=1的特殊情况。

 

 

codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

题目链接

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

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

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

To calculate the answer on every query let’s use the formula , where p1, p2, …, pk — all prime numbers which dividedn.

如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。

考虑两个数a,b的欧拉函数。

一开始考虑也许有什么性质。。。查了下欧拉函数的wiki
欧拉函数_维基百科
欧拉函数是积性函数(但不是完全积性函数。。因此必须phi(ab) =phi(a)*phi(b)成立当且仅当gcd(a,b)==1)

然而这里并不一定满足互质的条件。。。

 

再想一下。。。发现完全没必要由phi(a)和phi(b)得到phi(a*b)

直接把a*b看成一个数就好了。。。。

后面质因子乘积部分只需要把两部分的并在一起就好了。。。

所以根据上面欧拉函数的公式。。。答案分为两部分。。。

一部分是区间中所有数的乘积。。。

一部分是区间中所有数的不相同的素因子的p-1/p形式的乘积。。。

第一部分预处理前缀积即可。。。由于有%运算。。。所以除的时候需要计算逆元。。。

第二部分的做法同spoj_dquery解题报告

也是离线处理,把询问按照区间右端点排序升序排列,然后lst数组记录上次该数出现的位置。。。用bit维护一个从1到某个数的乘积。。。在撤销的时候同样需要逆元。。。

 

还要注意。。。太长的式子一定要分开写。。。。

因为写错括号顺序调了半天orz…