5022：Ene's problem

题目描述

Ene was a girl lives in computer systems. When she was studying the periodic sequence b_n = Bⁿ mod P (B is an integer and P is a prime number, n >= 0), she chose a contiguous subsequence b_s, b_{s + 1}, …, b_t, and marked them as special numbers. Then she began to investigate another sequence a_n = M × Aⁿ mod P, (M and A are integers) and incidentally such a problem came to her mind: what is the minimum non-negative integer k such that a_k is a special number(k starts from 0) ?

As a result of Ene's ability to control a computer, she soon answered the question of herself. But as she had never taken any computer science courses, she could only enumerate all possible solutions to get the answer. Your task is to solve her questions faster, so your algorithm should possess a lot higher performance than hers.

输入解释

There are no more than 100 test cases in the input. In each case, you are given six integers M, A, B, s, t, P, satisfying 2 ≤ A, B, M < P ≤ 10⁹，0 ≤ s ≤ t < P - 1, and P is a prime number. The input ends by 0 0 0 0 0 0.

输出解释

For each test case, output your answer k in one line. If there's no solution, output "impossible" (no quotes).

输入样例

2 3 5 1 6 11
2 3 8 1 6 11
0 0 0 0 0 0

输出样例

impossible
1

提示

   In the first test case, b1 = 5, b2 = 3, b3 = 4, b4 = 9, b5 = 1, b6 = 5, and a0 = 2, a1 = 6, a2 = 7, a3 = 10, a4 = 8, a5 = 2, it makes a cycle.
   On the other hand, in the second test case, b1 = 8, b2 = 9, b3 = 6, b4 = 4, b5 = 10, b6 = 3, and a0 = 2, a1 = 6 = b3. So that answer is 1.

来自杭电HDUOJ的附加信息

Recommend

hujie

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

题目来源 2014 ACM/ICPC Asia Regional Guangzhou Online

源链接： HDU-5022

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

共提交 0 次

通过率 --%

时间上限	内存上限
6000/3000MS(Java/Others)	65536/65536K(Java/Others)