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.
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.
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
私信点赞 评论 复制链接分享
- 回答 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
- 回答 1 已采纳 Problem Description 在网络课程上，我学到了很多有关IP的知识。IP全称叫网际协议，有时我们又用IP来指代我们的IP网络地址，现在IPV4下用一个32位无符号整数来表示，一般用点分方式来显示，点将IP地址分成4个部分，每个部分为8位，表示成一个无符号整数（因此不需要用正号出现），如192.168.100.16，是我们非常熟悉的IP地址，一个IP地址串中没有空格出现（因为要表示成一个32数字）。 但是粗心的我，常常将IP地址写错，现在需要你用程序来判断。 Input 输入有多个case，每个case有一行，不超过100个字符。 Output 对于每个case，判断输入的IP是否正确，如果正确输入YES，否则NO。 Sample Input 192.168.100.16 Sample Output YES
- 回答 1 已采纳 Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. !(http://acm.hdu.edu.cn/data/images/2311-1.png) Figure C-1: The top view of the cake !(http://acm.hdu.edu.cn/data/images/2311-2.png) Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10
- 回答 1 已采纳 Problem Description Accidentally, Cupid, god of desire has hurt himself with his own dart and fallen in love with Psyche. This has drawn the fury of his mother, Venus. The goddess then throws before Psyche a great mass of mixed crops. There are n heaps of crops in total, numbered from 1 to n. Psyche needs to arrange them in a certain order, assume crops on the i-th position is Ai. She is given some information about the final order of the crops: 1. the minimum value of A1,A2,...,Ai is Bi. 2. the maximum value of A1,A2,...,Ai is Ci. She wants to know the number of valid permutations. As this number can be large, output it modulo 998244353. Note that if there is no valid permutation, the answer is 0. Input The first line of input contains an integer T (1≤T≤15), which denotes the number of testcases. For each test case, the first line of input contains single integer n (1≤n≤105). The second line contains n integers, the i-th integer denotes Bi (1≤Bi≤n). The third line contains n integers, the i-th integer denotes Ci (1≤Ci≤n). Output For each testcase, print the number of valid permutations modulo 998244353. Sample Input 2 3 2 1 1 2 2 3 5 5 4 3 2 1 1 2 3 4 5 Sample Output 1 0
- 回答 1 已采纳 Problem Description ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not? We all know a master can have many prentices and a prentice may have a lot of masters too, it's legal. Nevertheless，some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian's master and, at the same time, 3xian is HH's master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not. Please note that the "master and prentice" relation is transitive. It means that if A is B's master ans B is C's master, then A is C's master. Input The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y's master and y is x's prentice. The input is terminated by N = 0. TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,..., N-1). We use their numbers instead of their names. Output For each test case, print in one line the judgement of the messy relationship. If it is legal, output "YES", otherwise "NO". Sample Input 3 2 0 1 1 2 2 2 0 1 1 0 0 0 Sample Output YES NO
- 回答 1 已采纳 Problem Description Farmer John's cows enjoy reading books, and FJ has discovered that his cows produce more milk when they read books of a somewhat intellectual nature. He decides to update the barn library to replace all of the cheap romance novels with textbooks on algorithms and mathematics. Unfortunately, a shipment of these new books has fallen in the mud and their ISBN numbers are now hard to read. An ISBN (International Standard Book Number) is a ten digit code that uniquely identifies a book. The first nine digits represent the book and the last digit is used to make sure the ISBN is correct. To verify that an ISBN number is correct, you calculate a sum that is 10 times the first digit plus 9 times the second digit plus 8 times the third digit ... all the way until you add 1 times the last digit. If the final number leaves no remainder when divided by 11, the code is a valid ISBN. For example 0201103311 is a valid ISBN, since 10*0 + 9*2 + 8*0 + 7*1 + 6*1 + 5*0 + 4*3 + 3*3 + 2*1 + 1*1 = 55. Each of the first nine digits can take a value between 0 and 9. Sometimes it is necessary to make the last digit equal to ten; this is done by writing the last digit as X. For example, 156881111X is a valid ISBN number. Your task is to fill in the missing digit from a given ISBN number where the missing digit is represented as '?'. Input * Line 1: A single line with a ten digit ISBN number that contains '?' in a single position Output * Line 1: The missing digit (0..9 or X). Output -1 if there is no acceptable digit for the position marked '?' that gives a valid ISBN. Sample Input 15688?111X Sample Output 1
- 回答 1 已采纳 Problem Description Xiao Ming is a citizen who's good at playing,he has lot's of gold cones which have square undersides,let's call them pyramids. Anyone of them can be defined by the square's length and the height,called them width and height. To easily understand,all the units are mile.Now Ming has n pyramids,there height and width are known,Xiao Ming wants to make them again to get two objects with the same volume. Of course he won't simply melt his pyramids and distribute to two parts.He has a sword named "Tu Long" which can cut anything easily. Now he put all pyramids on the ground (the usdersides close the ground)and cut a plane which is parallel with the water level by his sword ,call this plane cutting plane. Our mission is to find a cutting plane that makes the sum of volume above the plane same as the below,and this plane is average cutting plane.Figure out the height of average cutting plane. Input First line: T, the number of testcases.(1≤T≤100) Then T testcases follow.In each testcase print three lines : The first line contains one integers n(1≤n≤10000), the number of operations. The second line contains n integers A1,…,An(1≤i≤n,1≤Ai≤1000) represent the height of the ith pyramid. The third line contains n integers B1,…,Bn(1≤i≤n,1≤Bi≤100) represent the width of the ith pyramid. Output For each testcase print a integer - **the height of average cutting plane**. (the results take the integer part,like 15.8 you should output 15) Sample Input 2 2 6 5 10 7 8 702 983 144 268 732 166 247 569 20 37 51 61 39 5 79 99 Sample Output 1 98
- 回答 2 已采纳 用C语言编写一个对数组排序的程序，要求使用递归算法实现。
- 回答 1 已采纳 Problem Description Bob intends to color the nodes of a tree with a pen. The tree consists of N nodes. These nodes are numbered 1,2,...,N. The root of the tree is node 1. The initial color of each node is white. Bob can use one unit energy to color one node into black. To prevent Bob being lazy with painting, Alice proposed A+B rules. Each rule is represent by two numbers xi and yi. For the first A rules, it means that there should be no less than yi nodes painted black for the subtree of node xi. For the other B rules, it means that there should be no less than yi nodes painted black for all nodes except the subtree of node xi. You need to help Bob to calculate the minimum energy he needs for the painting with all rules proposed by Alice satisfied. Input The first line is the number of test cases. For each test case, the first line contains one positive number N(1≤N≤100000), indicating the number of trees nodes. The following N−1 lines describe the edges. Each line contains two integers u,v(1≤u,v≤N), denoting there is a edge between node u and node v. The following one line contains one number A(A≤100000), indicating the first A rules. The following A lines describe the first A rules. Each line contains two numbers xi and yi as described above. The following one line contains one number B(B≤100000), indicating the other B rules. The following B lines describe the other B rules. Each line contains two numbers xi and yi as described above. Output For each test case, output a integer donating the minimum energy Bob needs to use with all rules propose by Alice satisfied. If there is no solution, output −1 instead. Sample Input 2 5 1 2 2 3 3 4 1 5 2 2 1 5 1 1 2 1 5 1 2 2 3 3 4 1 5 3 1 2 2 2 5 1 1 3 5 Sample Output 2 -1
- 有大神有用C语言写的随机森林算法吗 python3年前回答 2 已采纳 因为想在C语言的基础上实现随机森林，但是搜集到的大多都是基于python。 所以，如果有大神能指教一下就太好了！跪谢~
- 回答 3 已采纳 Erlang中的变量大部分情况下是"不可变"的(进程数据区域等特殊的除外), 据称是和并行相关, 不过这里我比较困惑, 既然Erlang进程设置了消息系统, 理论上讲消息都是一个一个处理的, 即:同一个进程中的消息处理不存在并行情况, 因此无需要"边量不变". 如果是在多进程情况下, 由于进程的数据之间是切分开的, 看起来也不太需要"变量不变"这个特性, why??? 可否举个例子说明在哪种情况下需要"变量不变"这个特性??? 备注: 本人初学Erlang, 理解错误的地方希望前辈们指点. Thanks. [b]问题补充：[/b] 根据night_stalker的回答, 看起来immutable是和"并行"没有太大关系的了... 还有别的方面的特性决定需要使用immutable的么??? [b]问题补充：[/b] 感谢night_stalker, 又去查了下资料, 应该是和进程调度有关, 详细见这里 : http://hi.baidu.com/timeless/blog/item/3f3dafc3cb84835db319a8ae.html 感觉上是由于immutable的特性决定进程可以比较轻松的进行调度而不消耗太多资源, 想比传统的进程/线程方式就有了很多好出. 另, to night_stalker, Erlang里应该不直接支持global-var的把...每个进程都有自己独立的数据区域, 相互之间应该是不share的... 再次感谢, 对这个问题有了更深入的认识:)~
- 回答 1 已采纳 在看《erlang程序设计》中讲到5.3.2中提到的比特语法表达式里有这样的写法，但是翻来翻去都没找到关于#语法的解释 请指教！多谢
- 1年前TaiBai-let的博客 文章目录前言PID原理简单介绍位置型PID增量式PID位置型PID——C语言增量型PID——C语言积分分离的PID控制算法——C语言抗积分饱和的PID控制算法——C语言变积分的PID控制算法——C语言 前言 PID算法在工业应用中...
- 钱康来的博客 任何程序都要处理数据，计算机可以处理的数据有多种类型。在C语言程序中，用来保存数据的变量必须事先定义才能在程序中使用。定义变量的语法如下：变量类型名 变量名表;例如，以下语句定义了x、y、z三个变量名，其值...
- weixin_39777497的博客 yaoleiliu/Algorithmgithub.com知识点目录（持续更新中......）数据结构基础知识(含知识点及高频题)二叉树打印(TreePrint)先序遍历打印...序列化二叉树(递归、非递归)反序列化二叉树(递归、非递归)判断二叉树...
- weixin_39710288的博客 木叶医院，一名婴儿在几名医疗忍者的努力下，缓缓睁开了眼睛。”这，这孩子的眼睛？“ ——《火影之雪殇》做判断还记得上周的内容当中，我们有这样一段。 ...
- 2年前武器大师72的博客 如何用C语言实现呢？在网络搜索发现了一篇很好的博客，不过里面的数据又臭又长。在这里转载过来，重下新整理了一下。（原文链接）整理中发现，原文参考的 原理 在工业应用中PID及其衍生算法是应用最广泛的算法之一，...
- weixin_39880150的博客 插入类排序—(折半)插入排序、希尔排序交换类排序—冒泡排序、快速排序手撕图解归并类排序—归并排序(逆序数问题)计数排序引发的围观风波——一...的排序两分钟搞懂桶排序对于常见的快排、归并这些O(nlogn)的排序算法...
- 吮指原味张的博客 假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP的数学模型为： ...
- weixin_39992199的博客 不 BB，直接上干货，非科班出生，毕业工作后才开始学算法，到目前学了 4 年 ！...10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。掌握了这...