ACM程序設計-計算簡單題

簡單計算題ACM程序設計列出完數(shù)題目內(nèi)容自然數(shù)中，完數(shù)寥假設晨星，請在從1到某個整數(shù)范圍中打印出所有的完數(shù)來。所謂“完數(shù)”是指一個數(shù)恰好等于它的所有不同因子之和。例如，6是完數(shù)，因為6=1+2+3。而24不是完數(shù)，因為241+2+3+4+6+8+12(=36)。輸入描述輸入數(shù)據(jù)中含有一些整數(shù)n(1<n<10000)2輸出描述對于每個整數(shù)n，輸出所有不大于n的完數(shù)。每個整數(shù)n的輸出由n引導，跟上冒號，然后是由空格開道的一個個完數(shù)，每個n的完數(shù)列表應占獨立的一行。輸入樣例1005000輸出樣例100：6285000：6284963題目分析如果針對每個整數(shù)都搜索一次完數(shù)，時間會花費較多，由于完數(shù)較少，可以先找出10000以內(nèi)的所有完數(shù)，然后再針對n查表。4參考源代碼#include<stdio.h>intmain(void){ inti,j,k=0,n,sum,a[100]; for(i=2;i<10000;i+=2)//完數(shù)為偶數(shù) { sum=1; for(j=2;j<=i/2;j++) { if(i%j==0) sum+=j; } if(sum==i) a[k++]=i; }5參考源代碼 while(scanf("%d",&n)==1)

{ printf("%d:",n); for(i=0;i<k;i++) { if(a[i]<=n) printf("%d",a[i]); } printf("\n"); } return0;}6對稱三位數(shù)素數(shù)題目內(nèi)容判斷一個數(shù)是否為對稱三位數(shù)素數(shù)。所謂“對稱”是指一個數(shù)，倒過來還是該數(shù)。例如，375不是對稱數(shù)，因為倒過來變成了573。輸入描述輸入數(shù)據(jù)含有不多于50個的正整數(shù)(0<n<2^32)。輸出描述對于每個n，如果該數(shù)是對稱三位數(shù)素數(shù)，那么輸出“Yes”，否那么輸出“No”。每個判斷結果單獨一行。7輸入樣例11101272輸出樣例NoYesNo8題目分析三位對稱只須判斷個數(shù)與百位是否相等。9參考源代碼#include<stdio.h>#include<math.h>intisprime(inta){ inti; ints=(int)sqrt((double)a); for(i=2;i<=s;i++) { if(a%i==0) return0; } return1;}10參考源代碼intmain(void){ intn;

while(scanf("%d",&n)==1) { printf("%s",(n>100&&n<1000&&n/100==n%10&&isprime(n))?"Yes\n":"No\n"); } return0;}11五位以內(nèi)的對稱素數(shù)題目內(nèi)容判斷一個數(shù)是否為對稱且不大于五位數(shù)的素數(shù)。輸入描述輸入數(shù)據(jù)含有不多于50個的正整數(shù)n(0<n<2^32)。輸出描述對于每個n，如果該數(shù)是不大于五位數(shù)的對稱素數(shù)，那么輸出“Yes”，否那么輸出“No”。每個判斷結果單獨列一行。12輸入樣例11101272輸出樣例YesYesNo13題目分析怎樣判斷每位對稱素數(shù)？14參考源代碼#include<stdio.h>intisprime(intn){ inti; if(n==1)//1不是素數(shù) return0; if(n!=2&&n%2==0)//除開2以外的偶數(shù) return0; for(i=3;i*i<=n;i+=2)//恰好跳過2,3,5,7，它們是素數(shù) { if(n%i==0) return0; } return1;}15參考源代碼intissym(intn){ if(n<12&&n!=10)//1位是對稱數(shù)，2位素數(shù)中只有11是對稱的 return1; if(n>100&&n<1000&&n/100==n%10)//3位數(shù)中只須個位與百位相等 return1; //注意四位數(shù)不可能有對稱的素數(shù)，易得有11因子

if(n>10000&&n/1000==n%10*10+n/10%10) return1; return0;}16參考源代碼intmain(void){ intn;

while(scanf("%d",&n)==1) { printf("%s\n",n<100000&&issym(n)&&isprime(n)?"Yes":"No"); } return0;}17AneasyproblemTimeLimit:6000/3000MS(Java/Others)

MemoryLimit:32768/32768K(Java/Others)

18ProblemDescription

WhenTeddywasachild,hewasalwaysthinkingaboutsomesimplemathproblems,suchas“Whatit’s1cupofwaterplus1pileofdough..”,“100yuanbuy100pig”.etc..

OnedayTeddymetaoldmaninhisdream,inthatdreamthemanwhosenamewas“RuLai”gaveTeddyaproblem:

GivenanN,canyoucalculatehowmanywaystowriteNasi*j+i+j(0<i<=j)?

TeddyfoundtheanswerwhenNwaslessthan10…butifNgetbigger,hefounditwastoodifficultforhimtosolve.

Well,youcleverACMers,couldyouhelplittleTeddytosolvethisproblemandlethimhaveagooddream?19InputThefirstlinecontainaT(T<=2000).followedbyTlines,eachlinecontainanintegerN(0<=N<=).

OutputForeachcase,outputthenumberofwaysinoneline.20Sampleinput:213Sampleoutput:0121題目分析：思路1： 將等式變形為N+1=(i+1)*(j+1)，由于i<=j，只需要枚舉i〔枚舉范圍從1到〕，然后判斷是否滿足，直接計數(shù)即可。22思路2：同樣將等式變形N+1=(i+1)*(j+1)。只需要求出N+1的約數(shù)個數(shù)，然后分情況處理即可。令N+1的約數(shù)個數(shù)為f[N+1]1.當N+1為完全平方數(shù)時，ans=(f[N+1]–2+1)/2公式可以理解成：所有的約數(shù)，去掉1和本身之后〔減2〕，剩下的可以對稱的組成一對一對的答案。23而分解質(zhì)因數(shù)最有效的方法就是篩出范圍內(nèi)的素數(shù)表，然后依次試除。2.當N+１非完全平方數(shù)，同理可得，ans=(f[N+1]–2)/2。如何快速的求一個數(shù)N的約數(shù)個數(shù)我們知道,任何一個自然數(shù)N可以表示成其質(zhì)因數(shù)的冪的乘積的形式.由排列組合的乘法原理知，N的約數(shù)個數(shù)f[N]=(a1+1)*(a2+1)*…*(an+1)241、簡單的篩素數(shù)其思想是，先假定所有的數(shù)都是素數(shù)，然后從2開始依次篩掉素數(shù)的倍數(shù)的數(shù)。25constintMax=100000;boolbp[Max+1];//記錄每個數(shù)是否是素數(shù)intp[30000];//記錄篩選出來的素數(shù)intpCnt=0;//記錄當前篩選出來的素數(shù)個數(shù)voidsievePrime(){ inti,j;

memse