TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5413
  • 题目
  • P5413离散对数 模板题
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 20s 256MB
    问题描述

    给定素数 \(p\)\(T\) 次询问使得 \(a,b\) 满足 \(a^x \equiv b \pmod p\) 的最小非负整数 \(x\)

    输入格式

    第一行包含两个整数 \(T,p\)

    接下来 \(T\) 行,每行两个整数 \(a,b\) ,表示一组询问。

    输出格式

    输出共 \(T\) 行,每行一个非负整数,表示最小的 \(x\), 如果无解输出 \(-1\)

    样例输入

    15 83
    32 20
    55 48
    76 65
    14 38
    57 43
    24 59
    47 27
    6 28
    18 30
    1 82
    44 27
    40 42
    47 78
    77 45
    52 62

    样例输出

    55
    24
    54
    60
    13
    42
    70
    8
    12
    -1
    2
    -1
    60
    -1
    69

    提示

    对于 $20\%$ 的数据, \(p\leq 10^3\)

    对于 $40\%$ 的数据, \(p\leq 10^8\)

    对于 $60\%$ 的数据, \(p\leq 10^{12}\)

    对于 $80\%$ 的数据, \(p\leq 10^{18}\)

    对于 $100\%$ 的数据, $1\leq T\leq 200, 2\leq p\leq 3\times 10^{18}$ ,且 \(p\) 是素数。


    来源  原作者whzzt,由nodgd从loj6542搬运