bzoj 4802: 欧拉函数 费马小定理+根号求欧拉函数

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


我这个做法会被叉…用那个Carmichael数就可以叉掉费马小定理:如果p是素数,a<p,那么有a^(p-1) mod p = 1。

但是幸运的是数据没这么强,并且也没有特殊的去卡暴力,所以就非常爽了

先用费马小定理判断是否是素数,如果是就直接输出n-1,不是就跑一遍n^2暴力(为了防止被某些数据卡掉,所以我采用双指针往中间扫,这样某些数据就可以暴力过了)。

奇怪的做法却在第一页的代码:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注