5-2 模运算的逆元

5-2 模运算的逆元

童年时你学会的求余运算,更专业的名称是模运算。进入大学后,小明和小璐知道了模运算中逆元的概念。
已知互质的正整数n和a,a<n,将n作为模,则a的逆元b是满足如下条件的正整数:b<n并且(a*b)%n=1。实际上a的逆元是唯一的。
例如:设n=9,a=2,n和a互质,a的唯一的逆元b是5。
输入二行,第1行是整数n(n<10000)和k个正整数(k<100)。第2行是k个大于1的正整数a1, a2,……, ak,均小于n,用空格分开。
输出一行,k个整数。分别表示a1, a2,……, ak的逆元。若ai与n不互质,则对应输出0。

测试案例:
输入

9 7
5 6 7 8 2 3 4

输出:

2 0 4 8 5 0 7

信息

难度
5
分类
(无)
标签
递交数
214
已通过
80
通过率
37%
被复制
3
上传者

相关

在下列比赛中:

课程赛事2018-12-22