/ / 题库 /

5-2 模运算的逆元

5-2 模运算的逆元

测试数据来自 nnu_contest/5c1c90c3f41362709ec4a97d

童年时你学会的求余运算,更专业的名称是模运算。进入大学后,小明和小璐知道了模运算中逆元的概念。
已知互质的正整数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

信息

ID
1111
难度
9
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
上传者