6632：discrete logarithm problem

题目描述

You are given three integers $p, a, b$, where $p$ is a prime number and $p-1$ only has prime factors $2$ and/or $3$. Please find the minimum positive integer $x$ such that $a^x \equiv b \pmod{p}$.

输入解释

The first line contains an integer $T$ indicating there are $T$ tests. Each test consists of a single line containing three integers: $p, a, b$.

* $T \le 200$

* $65537 \le p \le 10^{18}$

* the prime factors of $p-1$ can only be $2$ or $3$

* $2 \le a, b \le p-1$

输出解释

For each test, output a line containing an integer $x$, representing the minimum positive value such that $a^x \equiv b \pmod{p}$. If there didn't exist any such number $x$, please output $-1$.

输入样例

6
65537 2 3
65537 2 4
65537 3 4
65537 4 4
65537 5 4
666334875701477377 2 3

输出样例

-1
2
45056
1
36864
1957714645490451

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2019 Multi-University Training Contest 5

源链接： HDU-6632

最后修改于 2020-10-25T23:33:01+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
3000/1500MS(Java/Others)	262144/262144K(Java/Others)