# Ene's problem

Problem Description

Ene was a girl lives in computer systems. When she was studying the periodic sequence bn = Bn mod P (B is an integer and P is a prime number, n >= 0), she chose a contiguous subsequence bs, bs + 1, …, bt, and marked them as special numbers. Then she began to investigate another sequence an = M × An 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 ak 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.

Input

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 ≤ 109，0 ≤ s ≤ t < P - 1, and P is a prime number. The input ends by 0 0 0 0 0 0.

Output

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

Sample Input

2 3 5 1 6 11

2 3 8 1 6 11

0 0 0 0 0 0

Sample Output

impossible

1

- 点赞
- 写回答
- 关注问题
- 收藏
- 复制链接分享
- 邀请回答

*1*条回答

#### 相关推荐

- 4年前回答 1 已采纳 Problem Description Ene was a girl lives in computer systems. When she was studying the periodic sequence bn = Bn mod P (B is an integer and P is a prime number, n >= 0), she chose a contiguous subsequence bs, bs + 1, …, bt, and marked them as special numbers. Then she began to investigate another sequence an = M × An 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 ak 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. Input 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 ≤ 109，0 ≤ s ≤ t < P - 1, and P is a prime number. The input ends by 0 0 0 0 0 0. Output For each test case, output your answer k in one line. If there's no solution, output "impossible" (no quotes). Sample Input 2 3 5 1 6 11 2 3 8 1 6 11 0 0 0 0 0 0 Sample Output impossible 1
- 回答 2 已采纳 In the planet w-503 of galaxy cgb, there is a kind of intelligent creature named QS. QScommunicate with each other via networks. If two QS want to get connected, they need to buy two network adapters (one for each QS) and a segment of network cable. Please be advised that ONE NETWORK ADAPTER CAN ONLY BE USED IN A SINGLE CONNECTION.(ie. if a QS want to setup four connections, it needs to buy four adapters). In the procedure of communication, a QS broadcasts its message to all the QS it is connected with, the group of QS who receive the message broadcast the message to all the QS they connected with, the procedure repeats until all the QS's have received the message. A sample is shown below: A sample QS network, and QS A want to send a message. Step 1. QS A sends message to QS B and QS C; Step 2. QS B sends message to QS A ; QS C sends message to QS A and QS D; Step 3. the procedure terminates because all the QS received the message. Each QS has its favorate brand of network adapters and always buys the brand in all of its connections. Also the distance between QS vary. Given the price of each QS's favorate brand of network adapters and the price of cable between each pair of QS, your task is to write a program to determine the minimum cost to setup a QS network. Input The 1st line of the input contains an integer t which indicates the number of data sets. From the second line there are t data sets. In a single data set,the 1st line contains an interger n which indicates the number of QS. The 2nd line contains n integers, indicating the price of each QS's favorate network adapter. In the 3rd line to the n+2th line contain a matrix indicating the price of cable between ecah pair of QS. Constrains: all the integers in the input are non-negative and not more than 1000. Output for each data set,output the minimum cost in a line. NO extra empty lines needed. Sample Input 1 3 10 20 30 0 100 200 100 0 300 200 300 0 Sample Output 370
- 回答 1 已采纳 Problem Description For any ACM/ICPC participant, it is always discouraging to discover that the real problems they face in the programming world are seldom as interesting as the tasks they face in the algorithm-related contests. While the efficiency of your algorithm is certainly vital to the overall system, still it is seldom valued so much as other factors such as readability, and the ability of coding accurately often takes precedence in many projects. Still, we judges believe that a balance between these two can be achieved - a good programmer should be able to come up with code that is fast, reliable and readable in a reasonable amount of time - and that is why you, the contestant, is asked to solve the problem of building a ranking system for us. You're probably familiar with the following paragraph taken from Rules of ACM/ICPC: A problem is solved when it is accepted by the judges. Teams are ranked according to the most problems solved. Teams who solve the same number of problems are ranked by least total time. The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the accepted run plus 20 penalty minutes for every rejected run for that problem regardless of submittal time. There is no time consumed for a problem that is not solved. During a contest, the following kinds of requests might be submitted by participants: Submission (Format: S [minute]:[Team No]:[Problem ID]:[Result]) If a team submits a problem which they have already solved, then this submission should be considered invalid and ignored by your system; otherwise, the submission is valid and saved for further processing - if the result is 1 (Correct), then this submission should be considered accepted by the system. Query a team's place on the rank list. (Format: R [Team No]) Sort the teams according to the contest rules mentioned above. A tie may occur between two teams who solved equal number of problems and same penalty. Two teams who solved same number of problems and have same penalty should always have same rank; however, when querying the Kth team on the rank list, even if many teams share the same rank, only one team should be printed (please refer to the rule given below). Query the Kth team on the rank list. (Format: T [k]) If a tie occurs, return the team with the minimum last accepted submission time. Note that the submission time of two teams might be different (i.e., in seconds) even though it may appear otherwise in the input. Initially every team has no submissions, and the contest will last no more than 5 hours. Input There are multiple test cases in the input. Each test case starts with two integers, N and M, (1 <= N <= 10000, 1 <= M <= 10), the number of teams participating in the competition, and the total number of problems in the contest. Teams are numbered from 0 to N - 1. Each of the following lines is either in one of the three formats listed above, or a single line "Contest Ends" followed by an empty line indicating the end of current test case. It is guaranteed that there are no more than 100000 requests in each test case. Input ends with End-of-File. Output For every submission request, if the submitted program is accepted, you need to output a line whose format is [Team No] [Problem ID]; for every query about team's place on the rank list, output the result in one single line; for every query about the team with the Kth highest score, if a team is found, output a line with one integer, the number of the team, or -1 if you are unable to find such a team. Please print a blank line after each test case. Sample Input 5 8 T 1 T 2 S 5:0:A:0 S 8:0:A:1 S 9:1:B:1 S 15:0:A:1 T 1 T 2 T 3 R 0 R 1 R 2 R 3 Contest Ends Sample Output 0 -1 [0][A] [1][B] 1 0 2 1 0 2 2
- 5年前回答 1 已采纳 Description Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N. "Oh, I know, I know!" Longge shouts! But do you know? Please solve it. Input Input contain several test case. A number N per line. Output For each N, output ,∑gcd(i, N) 1<=i <=N, a line Sample Input 2 6 Sample Output 3 15
- 4年前回答 1 已采纳 Problem Description Calculate S(n). S(n)=13+23 +33 +......+n3 . Input Each line will contain one integer N(1 < n < 1000000000). Process to end of file. Output For each case, output the last four dights of S(N) in one line. Sample Input 1 2 Sample Output 0001 0009
- 回答 1 已采纳 Problem Description Nowadays, many universities no longer force students to follow a fixed curriculum; instead they allow students to choose the courses on an individual basis. However, new programs need to be written to satisfy such needs. Your job is to write such a program. In our system, the following objects exist: Time Period, Course and Student. The relationships between the three objects are as follows: A course has a capacity, and is associated with multiple time periods; a student can register for multiple courses in the system (resulting in a possibly conflicting schedule). To resolve possible conflicts with the schedules as well as to ensure that the number of students registered for each course does not exceed its capacity, the system will use the logic described below to determine the result: Process courses, in the order they appear in the input. For each course: Check each student's request in the order it is received, and reject the request if a) accepting the request will result in a conflict in the student's schedule, or b) if no more students could be accepted by this class, or c) the student has already enrolled in this class; otherwise, the request is accepted. Can you solve this easy problem? Input There are multiple test cases in the input file. Each test case starts with three integers, N, M and R (1 <= N <= 20, 1 <= M <= 20, 0 <= R <= N * M), the number of students, the number of courses, and the number of requests, respectively. Each of the following N lines contains one string, the ID of the student. The ID will contain no characters other than '0'...'9' The next part of each test case consists of M lines, each of which contains three integers, I, C, T, (C <= 100, T <= 30), the ID of the course, the capacity, and the number of time periods used by the course respectively; T more integers follows, representing the unique identifiers of the time periods. The description for the requests comes next, each line in the format of [Student ID](Space character)[Course ID], in the order as the requests are received. It is guaranteed that the requests are always valid, i.e., both the student ID and the course ID could be found in the description given above. Two consecutive test cases are separated by a blank line. Input ends with End-of-File. Output For each test case, print the total number of requests accepted by the system, in the format as indicated in the sample output. Sample Input 2 2 4 0 1 101 1 2 3 4 102 2 1 5 0 101 1 102 1 101 0 102 1 1 0 4 5 1 1 5 Sample Output Case 1: 3 Case 2: 0
- 回答 1 已采纳 Description Let G be a weighted graph, i.e., every edge in G is associated with a nonnegative integer weight. The length of a path is the sum of edge weights in the path. A shortest path between vertices r and s in G, denoted by PG(r, s), is defined as a path with the shortest length from r to s. The distance between vertices r and s, denoted by dG(r, s), is the length of the shortest path PG(r, s). For two vertices in a connected graph, there exists at least one shortest path between them. Let e = (u, v) be an edge in PG(r, s) with v closer to s than u (v may be s). Let G - e denote the subgraph obtained by removing edge e from G. A detour from u is the shortest path from u to s in G - e, or PG-e(u, s). Edge e is a detour -critical edge in PG(r, s) if the removal of e results in the maximum distance increment from u to s. In other words, if e is a detour -critical edge in PG(r, s), then dG-e(u, s) - dG(u, s) is maximum among all edges in PG(r, s). The longest detour problem is to find the maximum distance increment of a shortest path. ![](http://poj.org/images/1340_1.jpg) Figure 4: A weighted graph G. For example, see Figure 4. PG(4, 1) = is the shortest path from vertex 4 to vertex 1. Path is the detour from vertex 4 to vertex 1 if edge (4, 3) is removed. Path is the detour from vertex 3 to vertex 1 if edge (3, 2) is removed. Path is the detour from vertex 2 to vertex 1 if edge (2, 1) is removed. The detour -critical edge in PG(4, 1) is not edge (4, 3) or edge (2, 1) but edge (3, 2) since dG-(3,2)(3, 1) - dG(3, 1) = 600 - 200 = 400 is greater than dG-(4,3)(4, 1) - dG(4, 1) = 500 - 300 = 200 and dG-(2,1)(2, 1) - dG(2, 1) = 200 - 100 = 100. The algorithm for finding detours, as well as determining the detour-critical edges, is important from the viewpoint of network management. Due to a sudden edge failure from some vertex, the message must be retransmitted through a detour from the vertex adjacent to the faulty edge. Suppose that we have several networks. Each network is connected and contains at most n vertices, where 3 0 if (u, v) is an edge of G, and wu,v= 0 otherwise, where wu,v in a nonnegative integer. Note that any two elements in each line of an adjacency matrix are separated by a space. The last line of each test case represents the sequence of vertices in a given shortest path in which there is also a space between two vertices. Note that the first and the last vertices denote the source and the destination vertices, respectively. For example, the adjacency matrix of the graph in Figure 4 is shown in test case 3 of the sample input. Output For each test case, output the maximum distance increment caused by the detour-critical edge of the given shortest path in one line. Sample Input 3 3 0 10 20 10 0 10 20 10 0 3 2 1 4 0 10 10 30 10 0 30 0 10 30 0 10 30 0 10 0 4 3 1 2 6 0 100 0 0 100 200 100 0 100 0 100 400 0 100 0 100 500 0 0 0 100 0 500 300 100 100 500 500 0 0 200 400 0 300 0 0 4 3 2 1 Sample Output 20 30 400
- 4年前回答 2 已采纳 Problem Description Everyone knows that the letter “E” is the most frequent letter in the English language. In fact, there are one hundred sixteen E’s on this very page ... no, make that one hundred twenty one. Indeed, when spelling out integers it is interesting to see which ones do NOT use the letter “E”. For example 6030 (six thousand thirty) doesn’t. Nor does 4002064 (four million two thousand sixty four). It turns out that 6030 is the 64th positive integer that does not use an “E” when spelled out and 4002064 is the 838th such number. Your job is to find the n-th such number. Note: 1,001,001,001,001,001,001,001,001,000 is “one octillion, one septillion, one sextillion, one quintil-lion, one quadrillion, one trillion, one billion, one million, one thousand”. (Whew!) Input The input file will consist of multiple test cases. Each input case will consist of one positive integer n (less than 231) on a line. A 0 indicates end-of-input. (There will be no commas in the input.) Output For each input n you will print, with appropriate commas, the n-th positive integer whose spelling does not use an “E”. You may assume that all answers are less than 1028. Sample Input 1 10 838 0 Sample Output 2 44 4,002,064
- ThinkWon的博客 文章目录数据库基础知识为什么要使用数据库什么是SQL？什么是MySQL?数据库三大范式是什么mysql有关权限的表都有哪几个MySQL的binlog有有几种录入格式？分别有什么区别？数据类型mysql有哪些数据类型引擎MySQL存储...
- 菜瓜技术联盟的博客 Problem E: 求Sn=a+aa+aaa+…+aa…aaa（有n个a）之值 Time Limit: 1 Sec Memory Limit: 128 MB Description 求Sn=a+aa+aaa+…+aa…aaa（有n个a）之值，其中a是一个数字(1&lt;=a&lt;=9)。例如：2+22+...
- 2年前Wood_Du的博客 文章目录N-Puzzle ProblemPreviewN-Puzzle Problem:N-Puzzle Problem 的可解性判断AlgorithmsThree Stages and Related AlgorithmsFirst phase：所需解决样例以及最多时间：Algorithm：A*Code：Result:Second phase...
- 4年前Usher_Ou的博客 Problem E: 成绩排序 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 779 Solved: 635 [Submit][Status][Web Board] Description 定义Student类： 1. 数据成员string name和int score表示一个学生的姓名、...
- 起风了的博客 题目描述 请写一个程序，判断给定表达式中的括号是否匹配，表达式中的合法括号为”(“, “)”... } if(s.empty()) printf("yes\n"); else printf("no\n"); while(!s.empty()) s.pop(); } } return 0; }
- Muff_man的博客 Description 求出一些整数中的最大值和最小值。 ...每行为一个十进制的数字，全部由0～9...} printf("The maximum value is : %s\n",max); printf("The minimum value is : %s\n",min); return 0; }
- 起风了的博客 } if(s.empty()) printf("yes\n"); //栈为空表示合法 else printf("no\n"); //栈不空表示非法 while(!s.empty()) s.pop(); //此时如果栈不空的话，栈中会有残留，应将栈置空 } } return 0; }
- 郑三原阿的博客 Description 给出两个正整数，计算两个数相加需要多少次进位。 ... while(scanf("%s",str1)!... scanf("%s",str2);... printf("%d\n",flag);//输出进位次数 } return 0; }
- coordinate_blog的博客 C(S, i) = min \{C(S - {i}, j) + dist(j, i)\} C ( S , i ) = m i n { C ( S − i , j ) + d i s t ( j , i ) } 其中 j j j 属于 S S S ， j ≠ i j \neq i j ̸ = i 且 j ≠ 1 j \neq 1 j ̸ = 1 。 ...
- 青瑟只鸟的博客 E - A very hard mathematic problem Time Limit:1000MS Memory Limit:32768KB 64bitIO Format:%I64d & %I64u Description Haoren is very good at solving mathematic problems.Today he is working a
- 回答 1 已采纳 Problem Description E-pang Palace was built in Qin dynasty by Emperor Qin Shihuang in Xianyang, Shanxi Province. It was the largest palace ever built by human. It was so large and so magnificent that after many years of construction, it still was not completed. Building the great wall, E-pang Palace and Qin Shihuang's tomb cost so much labor and human lives that people rose to fight against Qin Shihuang's regime. Xiang Yu and Liu Bang were two rebel leaders at that time. Liu Bang captured Xianyang -- the capital of Qin. Xiang Yu was very angry about this, and he commanded his army to march to Xianyang. Xiang Yu was the bravest and the strongest warrior at that time, and his army was much more than Liu Bang's. So Liu Bang was frighten and retreated from Xianyang, leaving all treasures in the grand E-pang Palace untouched. When Xiang Yu took Xianyang, he burned E-pang Palce. The fire lasted for more than three months, renouncing the end of Qin dynasty. Several years later, Liu Bang defeated Xiangyu and became the first emperor of Han dynasty. He went back to E-pang Palace but saw only some pillars left. Zhang Liang and Xiao He were Liu Bang's two most important ministers, so Liu Bang wanted to give them some awards. Liu Bang told them: "You guys can make two rectangular fences in E-pang Palace, then the land inside the fences will belongs to you. But the corners of the rectangles must be the pillars left on the ground, and two fences can't cross or touch each other." To simplify the problem, E-pang Palace can be consider as a plane, and pillars can be considered as points on the plane. The fences you make are rectangles, and you MUST make two rectangles. Please note that the rectangles you make must be parallel to the coordinate axes. The figures below shows 3 situations which are not qualified(Thick dots stands for pillars): ![](http://acm.hdu.edu.cn/data/images/C558-1002-1.jpg) Zhang Liang and Xiao He wanted the total area of their land in E-pang Palace to be maximum. Please bring your computer and go back to Han dynasty to help them so that you may change the history. Input There are no more than 15 test case. For each test case: The first line is an integer N, meaning that there are N pillars left in E-pang Palace(4 <=N <= 30). Then N lines follow. Each line contains two integers x and y (0 <= x,y <= 200), indicating a pillar's coordinate. No two pillars has the same coordinate. The input ends by N = 0. Output For each test case, print the maximum total area of land Zhang Liang and Xiao He could get. If it was impossible for them to build two qualified fences, print "imp". Sample Input 8 0 0 1 0 0 1 1 1 0 2 1 2 0 3 1 3 8 0 0 2 0 0 2 2 2 1 2 3 2 1 3 3 3 0 Sample Output 2 imp
- 3年前tingfenghanlei的博客 size_t n_vars = N * 6 + (N - 1) * 2; // Setting the number of constraints size_t n_constraints = N * 6; // Initial value of the independent variables. // SHOULD BE 0 besides initial state. ...