BZOJ 2242 [SDOI2011] 计算器

发布于 2018-01-12  114 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2242

题意:给出 a,b,p, 分别求:

求\(a^b \ mod \ p\)

求最小的非负整数 x 满足 \(a\cdot x\equiv b \ (\ mod\ p \ )\)。

求最小的非负整数 x 满足 \(a^x\equiv b \ (\ mod\ p \ )\)。


这题数据强一点吧... 爆 long long 会死的很惨 ...

有一个没啥用的小优化,发现 p 不一定是质数,每次枚举上界处理到 phi(p) 即可,但是由于要暴力求 phi(p) 反而会变慢一点...

 


一个非常弱的准退役OIER