浙江大学acm答案完整版.docx

1、浙江大学acm答案完整版浙江大学acm答案完整版 求余运算 给出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倍对

2、M取余一定能遍历0到M-1） 只需证明的是，该余数中两两之间互不相等； 假设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的交换 / 1

3、000#include int main() int a,b,i,; scanf(%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 三

4、月 22nd, 这个题目是判断给定的步长和mod，判断所产生的随机数已经覆盖0mod-1中所有的数，如果是，则说明所选的步长和mod是一个Good choice，否则为bad choice.需要懂得的基本内容为线性同余产生随机数，链接：http:/zh.wikipedia.org/zh-cn/%E7%B7%9A%E6%80%A7%E5%90%8C%E9%A4%98%E6%96%B9%E6%B3%95Problem Descriptionwill be generated every MOD iterations of the function. Note that by the nature

5、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 series 0, 15, 10, 5 (

6、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 pseudo-random numbers

7、. 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 20 and either Good C

8、hoice 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 Bad Choice. After ea

9、ch 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的所有质因子的积能整除A ? 1；若M是4的倍数，A ? 1

10、也是；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);return 0;/ Problem Descr

11、iptionOK, 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. feng5166 says.But what is t

12、he 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 input contains several

13、 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 case, you have to ou

14、tput 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; mapm; for(i=0;in;i+) s

15、canf(%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 EverTime Limit: 2000/1

16、000 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 survive, he decided to c

17、reate 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 each letter in a plai

18、ntext 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 X Y ZPlain textV W X

19、 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 sets. Each data set wil

20、l 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 characters, inclusiv

21、e, 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 NRUTWYFSHJ FWJ YMJ WJ

22、XZQY 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 FIRST IN A LITTLE IBERIAN

23、 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; printf(%sn,b); else

24、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. Some of these applicati

25、ons 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, which is the number o

26、f 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() double t; t=(num*log(n

27、um) - 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 digits of the integer. If

28、 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 integer 24. Adding t

29、he 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 also the digital root of 39. InputThe input file will contain a list of positive integers, one per line. The end of the input will be indicated by an integer value of