#P6993. [2017年成都七中集训]数论

    ID: 6824 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 6 上传者: 标签>数论中国剩余定理CF2000模运算数学

[2017年成都七中集训]数论

数论

问题描述

n2n+nm≡x(modp).n^{2n}+n^m\equiv x\pmod p.

对于给定的 x,m,p,px,m,p,p 是质数,求一个可行的正整数 nn,满足上式

由于解不唯一,所以这题设有 Special Judge,支持检验高精度的 n

输入格式

从标准输入读入。

第一行三个非负整数 xx,m,pp

输出格式

向标准输出写出。

输出任意一个合法的 nn(数据保证有解)

样例输入

17 0 997

样例输出

2

数据规模与约定

测试点 xx mm pp
1、2 x≤px\le p m≤pm\le p p≤103p\le10^3
3—6 m=0m=0 p≤109+7p\le10^9+7
7—10 m<pm<p

所有 pp 均为质数。测试点3—10的质数可以认为很大,且随机生成。输入 x,mx,m 为非负整数,保证存在合法正整数解。

输出的 nn 必须是正整数,可以使用任意多位十进制数字。x=px=p 时,按同余式将其视为余数 00。