/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
正整数 N, M が与えられます。k = 0, 1, \dots, M-1 について次の問題を解いてください。
- 以下の条件を満たす正整数 t が存在するかを判定してください。また、存在する場合は最小値を求めてください。
- N^t の正の約数 x であって、x \equiv k \pmod{M} となるものが存在する。
制約
- 1 \leq N \leq 10^{14}
- 1 \leq M \leq 4 \times 10^5
- N, M は整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
M 行出力せよ。i 行目には、k=i-1 について問題文の条件を満たす正整数 t が存在する場合はその最小値を、存在しない場合は -1 を出力せよ。
入力例 1
6 7
出力例 1
-1 1 1 1 2 2 1
例えば k=3 の時、x=3 は N^1=6 の約数であり、かつ x\equiv k \pmod{M} を満たすので、問題文の条件を満たす最小の正整数 t は t=1 です。
入力例 2
4 8
出力例 2
2 1 1 -1 1 -1 -1 -1
入力例 3
1 5
出力例 3
-1 1 -1 -1 -1
Score : 525 points
Problem Statement
You are given positive integers N and M. For each k = 0, 1, \dots, M-1, solve the following problem.
- Determine whether there exists a positive integer t satisfying the following condition, and if it exists, find the minimum such t.
- There exists a positive divisor x of N^t such that x \equiv k \pmod{M}.
Constraints
- 1 \leq N \leq 10^{14}
- 1 \leq M \leq 4 \times 10^5
- N and M are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print M lines. The i-th line should contain the minimum positive integer t satisfying the condition in the problem statement for k=i-1 if such t exists, and -1 otherwise.
Sample Input 1
6 7
Sample Output 1
-1 1 1 1 2 2 1
For example, when k=3, x=3 is a divisor of N^1=6 and satisfies x\equiv k \pmod{M}, so the minimum positive integer t satisfying the condition is t=1.
Sample Input 2
4 8
Sample Output 2
2 1 1 -1 1 -1 -1 -1
Sample Input 3
1 5
Sample Output 3
-1 1 -1 -1 -1