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

2023 程序设计与竞赛(作业3:中秋和国庆)

未参加
状态
已结束
规则
OI
题目
13
开始于
2023-10-01 08:00
结束于
2023-10-01 20:00
持续时间
12.0 小时
主持人
参赛人数
75