【每周一练】第17期:乘法逆元
本帖最后由 xiaosi4081 于 2022-11-22 10:14 编辑static/image/hrline/1.gif
大家好，今天是每周一练的第17期
这次的每周一练由我帮助用户@高山 发帖
（老开头了
上一期：第16期
题目名称：
乘法逆元
题目介绍：
给定 n, p 求 1~n 中所有整数在模 p 意义下的乘法逆元这里 a 模 p 的乘法逆元定义为 ax≡1(modp) 的解题目样例：输入 #1
10 13
输出 #11
7
9
10
8
11
2
5
3
4
题目数据范围：1≤n≤3×106,n<p<20000528题目更多限制：时间限制：500 ms也就是说只能运算不上50000000次{:10_256:}题解：由于大家都不会，只能公布下题解了(不过要等)：
**** Hidden Message *****最佳答案列表：
第一名
第二名
第三名
禁止抄题解！一旦发现，扣分！
温馨提示：这道题看似简单，其实思路有点难{:10_256:}
@zhangjinxuan 陶帖！{:10_256:} 初中数学吗？{:10_257:}不废啊{:10_266:}
哎，没文化，真可怕{:10_245:} 行，我再仔细想{:10_282:} 样例？？ 我感觉这题可以用费马小定理做，但是很有可能还需要高精度 tommyyu 发表于 2022-11-22 09:20
我感觉这题可以用费马小定理做，但是很有可能还需要高精度
费马小定理过不去的哦 xiaosi4081 发表于 2022-11-22 09:21
费马小定理过不去的哦
那就直接枚举{:10_256:} xiaosi4081 发表于 2022-11-22 09:21
费马小定理过不去的哦
我感觉条件如果允许的话可以去打一个表{:10_256:} tommyyu 发表于 2022-11-22 09:29
我感觉条件如果允许的话可以去打一个表
打表是无法获得最佳答案的哦 n这么大，意思说每一次都得所以 O(1) ，或者 O(log) 求出来！怎么玩？
等等，二分……{:10_256:} zhangjinxuan 发表于 2022-11-22 09:43
n这么大，意思说每一次都得所以 O(1) ，或者 O(log) 求出来！怎么玩？
等等，二分……
二分只能针对一个数，所以不行 二分也不对，不会！放弃！ 题目都没看懂....{:10_266:}{:10_266:} WC，你多大呀？ 元豪 发表于 2022-11-22 18:55
WC，你多大呀？
小学六年级{:10_256:} xiaosi4081 发表于 2022-11-22 19:23
小学六年级
我也是...
以后要好好学习了！{:10_265:} 来看看。。。 这会儿题目是真的难了{:10_266:}
有没有哪位勇者，敢来挑战此题，成功者，我赏他5荣誉5鱼币！ 不错