#P5352. Number Theory

    ID: 4365 传统题 1000ms 512MiB 尝试: 8 已通过: 1 难度: 7 上传者: 标签>数论中国剩余定理CF2200模运算数学双向搜索byAekdyCoin

Number Theory

Number Theory

题目描述

给定非负整数 x,m,px,m,p,其中 pp 是质数。求任意一个满足下式的正整数 nn:

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

数据保证有解。原题使用 Special Judge,支持检验高精度的 nn。

输入格式

从标准输入读入一行三个非负整数 x,m,px,m,p。

输出格式

向标准输出写出任意一个合法的正整数 nn。

样例

输入

17 0 997

输出

2

数据范围

所有测试点均满足 x≤px\le p。具体限制如下:

测试点编号 mm pp
1∼21\sim2 m≤pm\le p p≤103p\le10^3
3∼63\sim6 m=0m=0 p≤109+7p\le10^9+7
7∼107\sim10 m≤pm\le p

原表备注:测试点 3∼103\sim10 的质数可以认为较大,且随机生成。

原题面 PDF

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