AT_abc482_f.Mod M Divisor

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given positive integers NN and MM. For each k=0,1,…,M−1k = 0, 1, \dots, M-1, solve the following problem.

  • Determine whether there exists a positive integer tt satisfying the following condition, and if it exists, find the minimum such tt.
    • There exists a positive divisor xx of NtN^t such that x≡k(modM)x \equiv k \pmod{M}.

给定正整数 NN 和 MM。对每个 k=0,1,…,M−1k = 0, 1, \dots, M-1,求解以下问题:

  • 判断是否存在正整数 tt 满足如下条件;若存在,求出满足条件的最小 tt:
    • 存在 NtN^t 的一个正因子 xx,使得 x≡k(modM)x \equiv k \pmod{M}。

输入格式

The input is given from Standard Input in the following format:

NN MM

输入从标准输入中以如下格式给出:

NN MM

输出格式

Print MM lines. The ii-th line should contain the minimum positive integer tt satisfying the condition in the problem statement for k=i−1k=i-1 if such tt exists, and −1-1 otherwise.

输出 MM 行。第 ii 行应包含满足题目陈述中条件的最小正整数 tt(对应 k=i−1k=i-1),若这样的 tt 存在;否则输出 −1-1。

输入输出样例

  • 输入#1

    6 7

    输出#1

    -1
    1
    1
    1
    2
    2
    1
  • 输入#2

    4 8

    输出#2

    2
    1
    1
    -1
    1
    -1
    -1
    -1
  • 输入#3

    1 5

    输出#3

    -1
    1
    -1
    -1
    -1

说明/提示

Sample 1 Explanation:
For example, when k=3k=3, x=3x=3 is a divisor of N1=6N^1=6 and satisfies x≡k(modM)x\equiv k \pmod{M}, so the minimum positive integer tt satisfying the condition is t=1t=1.

Constraints

  • 1≤N≤10141 \leq N \leq 10^{14}
  • 1≤M≤4×1051 \leq M \leq 4 \times 10^5
  • NN and MM are integers.

样例 1 解释:
例如,当 k=3k=3 时,x=3x=3 是 N1=6N^1=6 的一个因数,且满足 x≡k(modM)x\equiv k \pmod{M},因此满足条件的最小正整数 tt 为 t=1t=1。

约束条件

  • 1≤N≤10141 \leq N \leq 10^{14}
  • 1≤M≤4×1051 \leq M \leq 4 \times 10^5
  • NN 和 MM 均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页