Home => ProblemSet => 【模板】模意义下的乘法逆元
Problem2275--【模板】模意义下的乘法逆元

2275: 【模板】模意义下的乘法逆元

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定 n,p 求 1∼n 中所有整数在模 p 意义下的乘法逆元。
这里 a 模 p 的乘法逆元定义为 ax≡1(mod p) 的解。

Input

一行两个正整数 n,p。

Output

输出 n 行，第 i 行表示 i 在模 p 下的乘法逆元。

Sample Input Copy 

10 13

Sample Output Copy 

1
7
9
10
8
11
2
5
3
4

HINT

1≤n≤3×106，n<p<20000528。
输入保证 p 为质数。

Source/Category

逆元 算法 数论 
[ Submit ] [ Status ]