资源描述:
《浙江大学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