资源描述：
《浙江大学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到
2、M-1）只需证明的是，该余数中两两之间互不相等；假设k*S和b*S对M取余相等（k和b∈[0,M)，并且k和b不等);则k*S=q1*M+r=q2*M+r=b*S<==>（k-b)*S=M*(q1-q2);S与M互质，由上式子可得M
3、（k-b），与k和b∈[0,M)，并且k和b不等矛盾；因此得证；另外，偶然看到一个很牛叉的辗转相除法；intgcd(inta,intb){while(b)b^=a^=b^=a%=b;returna;}此代码，很好很强大；把涉及位运算的交换的程序加入，便到得这段简洁高效的代码；注：A和B；经过A^=B^=A^=B，结果就得到A和B的交换/
4、///////////////////////////1000#includeintmain(){inta,b,i,;scanf("%d",&a);for(i=1;i<=a;i++){intsum=0;sum=sum+i;printf("%d",sum);}return0;};1001;#include"stdio.h"intmain(){unsigned_int64n;unsigned_int64temp;while(scanf("%I64u",&n)!=EOF)//是i非L{temp=(1+n)*n/2;printf("%I64u"
5、,temp);}return0;}//////////////////HDUACM1014UniformGenerator三月22nd,http://acm.hdu.edu.cn/showproblem.php?pid=1014这个题目是判断给定的步长和mod，判断所产生的随机数已经覆盖0~mod-1中所有的数，如果是，则说明所选的步长和mod是一个Goodchoice，否则为badchoice.需要懂得的基本内容为线性同余产生随机数，链接：http://zh.wikipedia.org/zh-cn/%E7%B7%9A%E6%80%A7%E5%90%8C%E9%A4
6、%98%E6%96%B9%E6%B3%95ProblemDescriptionComputersimulationsoftenrequirerandomnumbers.Onewaytogeneratepseudo-randomnumbersisviaafunctionoftheformseed(x+1)=[seed(x)+STEP]%MODwhere'%'isthemodulusoperator.Suchafunctionwillgeneratepseudo-randomnumbers(seed)between0andMOD-1.Oneproblemwithfunc
7、tionsofthisformisthattheywillalwaysgeneratethesamepatternoverandover.Inordertominimizethiseffect,selectingtheSTEPandMODvaluescarefullycanresultinauniformdistributionofallvaluesbetween(andincluding)0andMOD-1.Forexample,ifSTEP=3andMOD=5,thefunctionwillgeneratetheseriesofpseudo-randomnumb
8、ers0,3,1,4,2inarepeatingcycle.Inthisexample,allofthenumbersbetweenandincluding0andMOD-1willbegeneratedeveryMODiterationsofthefunction.Notethatbythenatureofthefunctiontogeneratethesameseed(x+1)everytimeseed(x)occursmeansthatifafunctionwillgenerateallthenumbersbetween0andMOD-1,itwillge
