模平方根问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

设p是一个奇素数,1≤x≤p-1,如果存在一个整数y,使得
则称y是x 的模p平方根。例如63 是55 的模103 平方根。试设计一个求整数x 的模p平方根的拉斯维加斯算法。算法的计算时间应为log p 的多项式。
设计一个拉斯维加斯算法,对于给定的奇素数p和整数x,计算x的模p平方根。

Input

输入数据只有一行,有2 个正整数p和x。p≤1000000。

Output

将计算出的x 的模p平方根输出。当不存在x 的模p平方根时,输出0。

Sample Input

103 55

Sample Output

63

Hint

 

Source