浙江大学acm答案完整版

1、 求余运算 给出S和M，求0*S%M，1*S%M，2*S%M.(M-1)*S%M能否组成一个集合包含0.1.。M-1；（这个是原题意改造而来）；算法：判断两个数是否互质；or 暴力解决其实暴力完全可以解决这个问题（b），只是其中用数学方法更加高效，巧妙；证明如果S和M互质则满足题意：另G=gcd(S,M);则S=A*G，M=B*G；另X=K*S%M=K*S-T*M（T为整数，满足X属于0到M-1）；X=K*A*G-T*B*G;因此取余后的整数一定是G的倍数，G只能取1才能满足条件；充分性的证明：（即当S与M互质，则0到M-1的S倍对M取余一定能遍历0到M-1）只需证明的是，该余数中两两之间互不

2、相等；假设k*S和b*S对M取余相等（k和b0,M)，并且k和b不等);则k*S=q1*M+r=q2*M+r=b*S （k-b)*S=M*(q1-q2);S与M互质，由上式子可得M|（k-b），与k和b0,M)，并且k和b不等矛盾；因此得证；另外，偶然看到一个很牛叉的辗转相除法；int gcd(int a,int b)while(b) b=a=b=a%=b;return a;此代码，很好很强大；把涉及位运算的交换的程序加入，便到得这段简洁高效的代码；注：A和B；经过A=B=A=B，结果就得到A和B的交换 / 1000#include int main() int a,b,i,; scanf(%

3、d,&a); for(i=1;i=a;i+) int sum=0; sum=sum+i; printf(%dn,sum); return 0;1001; #includestdio.hint main() unsigned _int64 n; unsigned _int64 temp; while(scanf(%I64u,&n)!=EOF) /是i 非L temp=(1+n)*n/2;printf(%I64unn,temp);return 0;/ HDU ACM 1014 Uniform Generator 三月 22nd, 这个题目是判断给定的步长和mod，判断所产生的随机数已经覆盖0mod

4、-1中所有的数，如果是，则说明所选的步长和mod是一个Good choice，否则为bad choice.需要懂得的基本内容为线性同余产生随机数，链接：Problem DescriptionComputer simulations often require random numbers. One way to generate pseudo-random numbers is via a function of the formseed(x+1) = seed(x) + STEP % MODwhere % is the modulus operator. Such a function wi

5、ll generate pseudo-random numbers (seed) between 0 and MOD-1. One problem with functions of this form is that they will always generate the same pattern over and over. In order to minimize this effect, selecting the STEP and MOD values carefully can result in a uniform distribution of all values bet

6、ween (and including) 0 and MOD-1. For example, if STEP = 3 and MOD = 5, the function will generate the series of pseudo-random numbers 0, 3, 1, 4, 2 in a repeating cycle. In this example, all of the numbers between and including 0 and MOD-1 will be generated every MOD iterations of the function. Not

7、e that by the nature of the function to generate the same seed(x+1) every time seed(x) occurs means that if a function will generate all the numbers between 0 and MOD-1, it will generate pseudo-random numbers uniformly with every MOD iterations. If STEP = 15 and MOD = 20, the function generates the

8、series 0, 15, 10, 5 (or any other repeating series if the initial seed is other than 0). This is a poor selection of STEP and MOD because no initial seed will generate all of the numbers from 0 and MOD-1. Your program will determine if choices of STEP and MOD will generate a uniform distribution of

9、pseudo-random numbers. InputEach line of input will contain a pair of integers for STEP and MOD in that order (1 = STEP, MOD = 100000). OutputFor each line of input, your program should print the STEP value right- justified in columns 1 through 10, the MOD value right-justified in columns 11 through

10、 20 and either Good Choice or Bad Choice left-justified starting in column 25. The Good Choice message should be printed when the selection of STEP and MOD will generate all the numbers between and including 0 and MOD-1 when MOD numbers are generated. Otherwise, your program should print the message

11、 Bad Choice. After each output test set, your program should print exactly one blank line.Sample Input3 515 2063923 99999 Sample Output 3 5 Good Choice 15 20 Bad Choice 63923 99999 Good Choice线性同余方法（LCG）是个产生伪随机数的方法。它是根据递归公式：其中A,B,M是产生器设定的常数。LCG的周期最大为M，但大部分情况都会少于M。要令LCG达到最大周期，应符合以下条件：B,M互质；M的所有质因子的积能

12、整除A ? 1；若M是4的倍数，A ? 1也是；A,B,N0都比M小；A,B是正整数。由以上可知，本题的求解方案。代码如下：#include int main()int a, b, max, min, tmp;while (scanf(%d%d,&a,&b) != EOF)max = ab?a:b;min = ab?a:b;while (min)tmp = max%min;max = min;min = tmp;if (max=1) printf(%10d%10d Good Choicenn, a, b);else printf(%10d%10d Bad Choicenn, a, b);ret

13、urn 0;/ Problem DescriptionOK, you are not too bad, em. But you can never pass the next test. feng5166 says.I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers. feng51

14、66 says.But what is the characteristic of the special integer? Ignatius asks.The integer will appear at least (N+1)/2 times. If you cant find the right integer, I will kill the Princess, and you will be my dinner, too. Hahahaha. feng5166 says.Can you find the special integer for Ignatius? InputThe i

15、nput contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1=N=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the N integers. The input is terminated by the end of file. OutputFor each test

16、 case, you have to output only one line which contains the special number you have found. Sample Input51 3 2 3 3111 1 1 1 1 5 5 5 5 5 571 1 1 1 1 1 1 Sample Output351#include#include#include#includeusing namespace std;int main() int n,i,x; /freopen(a.txt,r,stdin); while(scanf(%d,&n)!=EOF) vectorv; m

17、apm; for(i=0;in;i+) scanf(%d,&x); mx+; n=(n+1)/2; map:iterator it; for(it=m.begin();it!=m.end();it+) if(it-second=n)v.push_back(it-first); sort(v.begin(),v.end(); if(v.size()=1) printf(%d,v0); for(i=1;iv.size();i+)printf( %d,vi); printf(n); return 0; / 1048;用100的AC热情，挑战39的高温加油! The Hardest Problem E

18、verTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5571 Accepted Submission(s): 2540Problem DescriptionJulius Caesar lived in a time of danger and intrigue. The hardest situation Caesar ever faced was keeping himself alive. In order for him to sur

19、vive, he decided to create one of the first ciphers. This cipher was so incredibly sound, that no one could figure it out without knowing how it worked. You are a sub captain of Caesars army. It is your job to decipher the messages sent by Caesar and provide to your general. The code is simple. For

20、each letter in a plaintext message, you shift it five places to the right to create the secure message (i.e., if the letter is A, the cipher text would be F). Since you are creating plain text out of Caesars messages, you will do the opposite: Cipher textA B C D E F G H I J K L M N O P Q R S T U V W

21、 X Y ZPlain textV W X Y Z A B C D E F G H I J K L M N O P Q R S T U Only letters are shifted in this cipher. Any non-alphabetical character should remain the same, and all alphabetical characters will be upper case. InputInput to this problem will consist of a (non-empty) series of up to 100 data se

22、ts. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets. All characters will be uppercase. A single data set has 3 components: Start line - A single line, START Cipher message - A single line containing from one to two hundred

23、 characters, inclusive, comprising a single message from Caesar End line - A single line, END Following the final data set will be a single line, ENDOFINPUT. OutputFor each data set, there will be exactly one line of output. This is the original message by Caesar. Sample InputSTARTNS BFW, JAJSYX TK

24、NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJXENDSTARTN BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJENDSTARTIFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJENDENDOFINPUT Sample OutputIN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSESI WOULD RATHER BE FIRS

25、T IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROMEDANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE #include #include int main() char a15; char b100; char c15; int j; for(;) gets(a); if(!strcmp(a,START) gets(b); gets(c); if(!(strcmp(c,END) for(j=0;bj!=0;j+) if(bj=F & bj=A & bj=E) bj=bj+21;

26、 printf(%sn,b); else if(!strcmp(a,ENDOFINPUT) break; return 0; / 1018 Big NumberTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 8372 Accepted Submission(s): 3701Problem DescriptionIn many applications very large integers numbers are required. So

27、me of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number, you have to determine the number of digits in the factorial of the number. InputInput consists of several lines of integer numbers. The first line contains an integer n,

28、which is the number of cases to be tested, followed by n lines, one integer 1 n 107 on each line. OutputThe output contains the number of digits in the factorial of the integers appearing in the input. Sample Input21020 Sample Output719 #include#include#define pi 3.14159265int num,result;void JC() d

29、ouble t; t=(num*log(num) - num + 0.5*log(2*num*pi)/log(10); /经典的转换技巧 result = (int)t+1; printf(%dn,result);int main() int i,n; scanf(%d,&n); for( i=0 ; in ; i+ ) /求阶乘共用多少位，经典常用 scanf(%d,&num); JC(); return 0;/ 1013Problem DescriptionThe digital root of a positive integer is found by summing the digi

30、ts of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.For example, consider the positive

31、 integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 yeilds 3, a single digit and a

32、lso the digital root of 39. InputThe input contain a list of positive integers, one per line. The end of the input will be indicated by an integer value of zero. OutputFor each integer in the input, output its digital root on a separate line of the output. Sample Input24390 Sample Output63#include #

33、include using namespace std;int Digit(int n) int digit=0; while(true) digit=0; while(n) digit+=n%10; /这步很经典，常用数字的判断及各位数的存取。如123 ，可以得出， /百位为1，十位为2；等等！ n/=10; if(digits) sum=0; for(i=0; is) for(i=0; is.size(); +i) /还在这里，求和，/求各个字符时，用这行也可以 sum+=si-0;*/ if(sum=0) break; digit=Digit(sum); coutdigitendl; r

34、eturn 0; / 1032 Problem DescriptionProblems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.Consider the

35、following algorithm: 1. input n 2. print n 3. if n = 1 then STOP 4. if n is odd then n - 3n + 1 5. else n - n / 2 6. GOTO 2Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured that the algorithm above will terminate (when

36、a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 n 1,000,000 (and, in fact, for many more numbers than this.) Given an input n, it is possible to determi

37、ne the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16. For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j. InputThe input will consist of a ser

38、ies of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0. You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j. You can assume that no opperati

39、on overflows a 32-bit integer. OutputFor each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output f

40、or each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line). Sample Input1 10100 200201 210900 1000 Sample Output1 10 20100 200 125201 210 89900 1000 174#includeusing

41、 namespace std;int main() int m,n,lenm,lenn; while(cinmn) int start=m,end=n,i,max=0; if(startend) int temp=start; start=end; end=temp; / /if for(i=start;i=end;i+) int count=1,temp=i; while(temp!=1) if(temp%2!=0) temp=3*temp+1; else temp/=2; count+; /while if(maxcount) max=count; / coutcount ; /for c

42、outm n maxendl; /while return 0;/ 1040/必看的，也是 必会的！ As Easy As A+BTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 12053 Accepted Submission(s): 4798Problem DescriptionThese days, I am thinking about a question, how can I get a problem as easy as A+

43、B? It is fairly difficulty to do such a thing. Of course, I got it after many waking nights.Give you some integers, your task is to sort these number ascending (升序).You should know how easy the problem is now!Good luck!InputInput contains multiple test cases. The first line of the input is a single

44、integer T which is the number of test cases. T test cases follow. Each test case contains an integer N (1=N=1000 the number of integers to be sorted) and then N integers follow in the same line. It is guarantied that all integers are in the range of 32-int. OutputFor each case, print the sorting res

45、ult, and one line one case. Sample Input23 2 1 39 1 4 7 2 5 8 3 6 9 Sample Output1 2 31 2 3 4 5 6 7 8 9#includevoid main() int n,i,m,j,k,t,l,a10000; scanf(%d,&n); for(i=0;in;i+) scanf(%d,&m); for(j=0;jm;j+) scanf(%d,&aj); for(k=0;km;k+) for(t=0;tat+1) l=at; at=at+1; at+1=l; for(j=0;jm;j+) printf(%d,

46、aj); if(jm-1) /就这两步要小心谨慎，陷阱，有时不用多加换行服！ printf( ); printf(n); / 1042 N!Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 17235 Accepted Submission(s): 4385Problem DescriptionGiven an integer N(0 N 10000), your task is to calculate N! InputOne N in o

47、ne line, process to the end of file. OutputFor each N, output N! in one line. Sample Input123 Sample Output126include#includeint main() int n,k,t,p,sum,j,i; int s40000; while(scanf(%d,&n)!=EOF) k=0; t=0; p=0; sum=0; s0=1; for(j=1;j=n;j+) for(i=0;i9) si=sum%10; p=sum/10; if(t=i) t+; st=0; /看不明白 else si=sum; for(i=t;i=0;i-) printf(%d,si); printf(n)