ACM程序设计-计算简单题.ppt

,简单计算题,ACM程序设计,2/31,列出完数,题目内容自然数中，完数寥若晨星，请在从1到某个整数范围中打印出所有的完数来。所谓“完数”是指一个数恰好等于它的所有不同因子之和。例如，6是完数，因为6=1+2+3。而24不是完数，因为241+2+3+4+6+8+12(=36)。输入描述输入数据中含有一些整数n(1n10000),3/31,输出描述对于每个整数n，输出所有不大于n的完数。每个整数n的输出由n引导，跟上冒号，然后是由空格开道的一个个完数，每个n的完数列表应占独立的一行。输入样例1005000输出样例100：6285000：628496,4/31,题目分析,如果针对每个整数都搜索一次完数，时间会花费较多，由于完数较少，可以先找出10000以内的所有完数，然后再针对n查表。,5/31,参考源代码,#includeintmain(void)inti,j,k=0,n,sum,a100;for(i=2;i10000;i+=2)/已知完数为偶数sum=1;for(j=2;j=i/2;j+)if(i%j=0)sum+=j;if(sum=i)ak+=i;,6/31,参考源代码,while(scanf(%d,7/31,对称三位数素数,题目内容判断一个数是否为对称三位数素数。所谓“对称”是指一个数，倒过来还是该数。例如，375不是对称数，因为倒过来变成了573。输入描述输入数据含有不多于50个的正整数(0n232)。输出描述对于每个n，如果该数是对称三位数素数，则输出“Yes”，否则输出“No”。每个判断结果单独一行。,8/31,输入样例11101272输出样例NoYesNo,9/31,题目分析,三位对称只须判断个数与百位是否相等。,10/31,参考源代码,#include#includeintisprime(inta)inti;ints=(int)sqrt(double)a);for(i=2;i=s;i+)if(a%i=0)return0;return1;,11/31,参考源代码,intmain(void)intn;while(scanf(%d,12/31,五位以内的对称素数,题目内容判断一个数是否为对称且不大于五位数的素数。输入描述输入数据含有不多于50个的正整数n(0n232)。输出描述对于每个n，如果该数是不大于五位数的对称素数，则输出“Yes”，否则输出“No”。每个判断结果单独列一行。,13/31,输入样例11101272输出样例YesYesNo,14/31,题目分析,怎样判断每位对称素数？,15/31,参考源代码,#includeintisprime(intn)inti;if(n=1)/1不是素数return0;if(n!=2,16/31,参考源代码,intissym(intn)if(n100,17/31,参考源代码,intmain(void)intn;while(scanf(%d,18/31,Aneasyproblem,TimeLimit:6000/3000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others),19/31,ProblemDescriptionWhenTeddywasachild,hewasalwaysthinkingaboutsomesimplemathproblems,suchas“Whatits1cupofwaterplus1pileofdough.”,“100yuanbuy100pig”.etc.OnedayTeddymetaoldmaninhisdream,inthatdreamthemanwhosenamewas“RuLai”gaveTeddyaproblem:GivenanN,canyoucalculatehowmanywaystowriteNasi*j+i+j(0i=j)?TeddyfoundtheanswerwhenNwaslessthan10butifNgetbigger,hefounditwastoodifficultforhimtosolve.Well,youcleverACMers,couldyouhelplittleTeddytosolvethisproblemandlethimhaveagooddream?,20/31,InputThefirstlinecontainaT(T=2000).followedbyTlines,eachlinecontainanintegerN(0=N=).OutputForeachcase,outputthenumberofwaysinoneline.,21/31,Sampleinput:213Sampleoutput:01,22/31,题目分析：,思路1：将等式变形为N+1=(i+1)*(j+1)，由于i=j，只需要枚举i（枚举范围从1到），然后判断是否满足，直接计数即可。,23/31,思路2：同样将等式变形N+1=(i+1)*(j+1)。只需要求出N+1的约数个数，然后分情况处理即可。令N+1的约数个数为fN+11.当N+1为完全平方数时，ans=(fN+12+1)/2公式可以理解成：所有的约数，去掉1和本身之后（减2），剩下的可以对称的组成一对一对的答案。,24/31,而分解质因数最有效的方法就是筛出范围内的素数表，然后依次试除。,2.当N+非完全平方数，同理可得，ans=(fN+12)/2。如何快速的求一个数N的约数个数我们知道,任何一个自然数N可以表示成其质因数的幂的乘积的形式.,由排列组合的乘法原理知，N的约数个数fN=(a1+1)*(a2+1)*(an+1),25/31,1、简单的筛素数,其思想是，先假定所有的数都是素数，然后从2开始依次筛掉素数的倍数的数。,26/31,constintMax=100000;boolbpMax+1;/记录每个数是否是素数intp30000;/记录筛选出来的素数intpCnt=0;/记录当前筛选出来的素数个数voidsievePr