第四周簡(jiǎn)單題三

1、第四講關(guān)于數(shù)的一些簡(jiǎn)單問(wèn)題ACM算法與程序設(shè)計(jì)7/23/20221列出完數(shù)題目?jī)?nèi)容 自然數(shù)中，完數(shù)寥若晨星，請(qǐng)?jiān)趶?到某個(gè)整數(shù)范圍中打印出所有的完數(shù)來(lái)。所謂“完數(shù)”是指一個(gè)數(shù)恰好等于它的所有不同因子之和。例如，6是完數(shù)，因?yàn)?=1+2+3。而24不是完數(shù)，因?yàn)?24 1+2+3+4+6+8+12(=36)。輸入描述 輸入數(shù)據(jù)中含有一些整數(shù)n(1n10000)7/23/20222輸出描述 對(duì)于每個(gè)整數(shù)n，輸出所有不大于n的完數(shù)。每個(gè)整數(shù)n的輸出由n引導(dǎo)，跟上冒號(hào)，然后是由空格開(kāi)道的一個(gè)個(gè)完數(shù)，每個(gè)n的完數(shù)列表應(yīng)占獨(dú)立的一行。輸入樣例 100 5000輸出樣例 100： 6 28 5000： 6

2、28 4967/23/20223題目分析如果針對(duì)每個(gè)整數(shù)都搜索一次完數(shù)，時(shí)間會(huì)花費(fèi)較多，由于完數(shù)較少，可以先找出10000以內(nèi)的所有完數(shù)，然后再針對(duì)n查表。7/23/20224參考源代碼#include int main(void)int i,j,k=0,n,sum,a100;for(i=2;i10000;i+=2) /完數(shù)一定為偶數(shù)sum=1;for(j=2;j=i/2;j+)if(i%j=0)sum+=j;if(sum=i)ak+=i;7/23/20225參考源代碼while(scanf(%d,&n)=1)printf(%d: ,n);for(i=0;ik;i+)if(ai=n)print

3、f(%d ,ai);printf(n);return 0;7/23/20226對(duì)稱三位數(shù)素?cái)?shù)題目?jī)?nèi)容 判斷一個(gè)數(shù)是否為對(duì)稱三位數(shù)素?cái)?shù)。所謂“對(duì)稱”是指一個(gè)數(shù)，倒過(guò)來(lái)還是該數(shù)。例如，375不是對(duì)稱數(shù)，因?yàn)榈惯^(guò)來(lái)變成了573。輸入描述 輸入數(shù)據(jù)含有不多于50個(gè)的正整數(shù)(0n232)。輸出描述 對(duì)于每個(gè)n，如果該數(shù)是對(duì)稱三位數(shù)素?cái)?shù)，則輸出“Yes”，否則輸出“No”。每個(gè)判斷結(jié)果單獨(dú)一行。7/23/20227輸入樣例 11 101 272輸出樣例 No Yes No7/23/20228題目分析三位對(duì)稱只須判斷個(gè)數(shù)與百位是否相等。7/23/20229參考源代碼#include #include int

4、 isprime(int a)int i;int s=(int)sqrt(double)a);for(i=2;i100&n1000 &n/100=n%10 &isprime(n) ?Yesn:Non);return 0;7/23/202211五位以內(nèi)的對(duì)稱素?cái)?shù)題目?jī)?nèi)容 判斷一個(gè)數(shù)是否為對(duì)稱且不大于五位數(shù)的素?cái)?shù)。輸入描述 輸入數(shù)據(jù)含有不多于50個(gè)的正整數(shù)n(0n232)。輸出描述 對(duì)于每個(gè)n，如果該數(shù)是不大于五位數(shù)的對(duì)稱素?cái)?shù)，則輸出“Yes”，否則輸出“No”。每個(gè)判斷結(jié)果單獨(dú)列一行。7/23/202212輸入樣例 11 101 272輸出樣例 Yes Yes No7/23/202213題目分析

5、怎樣判斷每位對(duì)稱素?cái)?shù)？7/23/202214參考源代碼#include int isprime(int n)int i;if(n=1) /1不是素?cái)?shù)return 0;if(n!=2&n%2=0)/除開(kāi)2以外的2偶數(shù)return 0;for(i=3;i*i=n;i+=2)/恰好跳過(guò)2,3,5,7，它們是素?cái)?shù)if(n%i=0)return 0;return 1;7/23/202215參考源代碼int issym(int n)if(n100&n10000&n/1000=n%10*10+n/10%10)return 1;return 0;7/23/202216參考源代碼int main(void)in

6、t n;while(scanf(%d,&n)=1)printf(%sn,n100000&issym(n) &isprime(n)?Yes:No);return 0;7/23/202217 An easy problemTime Limit: 6000/3000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)7/23/202218Problem Description When Teddy was a child , he was always thinking about some simple math problems ,

7、such as “What its 1 cup of water plus 1 pile of dough .” , “100 yuan buy 100 pig” .etc. One day Teddy met a old man in his dream , in that dream the man whose name was“RuLai” gave Teddy a problem :Given an N , can you calculate how many ways to write N as i * j + i + j (0 i = j) ?Teddy found the ans

8、wer when N was less than 10but if N get bigger , he found it was too difficult for him to solve.Well , you clever ACMers ,could you help little Teddy to solve this problem and let him have a good dream ?7/23/202219Input The first line contain a T(T = 2000) . followed by T lines ,each line contain an

9、 integer N (0=N = ).Output For each case, output the number of ways in one line. 7/23/202220Sample input: 2 1 3 Sample output: 0 17/23/202221題目分析：思路1： 將等式變形為 N + 1 = (i + 1) * (j + 1)，由于i = j，只需要枚舉i （枚舉范圍從1到 ），然后判斷是否滿足，直接計(jì)數(shù)即可。7/23/202222思路2： 同樣將等式變形N + 1 = (i + 1) * (j + 1)。只需要求出N + 1的約數(shù)個(gè)數(shù)，然后分情況處理即可

10、。令N + 1的約數(shù)個(gè)數(shù)為fN + 1 1. 當(dāng)N + 1為完全平方數(shù)時(shí)，ans = (fN + 1 2 + 1) / 2公式可以理解成：所有的約數(shù)，去掉1和本身之后（減2），剩下的可以對(duì)稱的組成一對(duì)一對(duì)的答案。7/23/202223而分解質(zhì)因數(shù)最有效的方法就是篩出 范圍內(nèi)的素?cái)?shù)表，然后依次試除。2. 當(dāng)N +非完全平方數(shù)，同理可得， ans = (fN + 1 2) / 2 。如何快速的求一個(gè)數(shù)N的約數(shù)個(gè)數(shù) 我們知道,任何一個(gè)自然數(shù)N可以表示成其質(zhì)因數(shù)的冪的乘積的形式.由排列組合的乘法原理知，N的約數(shù)個(gè)數(shù) fN = (a1 + 1) * (a2 + 1)*(an + 1)7/23/20222

11、41、簡(jiǎn)單的篩素?cái)?shù)其思想是，先假定所有的數(shù)都是質(zhì)數(shù)，然后從2開(kāi)始依次篩掉素?cái)?shù)的倍數(shù)的數(shù)。 7/23/202225const int Max = 100;bool bpMax + 1; /記錄每個(gè)數(shù)是否是素?cái)?shù)int p30; /記錄篩選出來(lái)的素?cái)?shù)int pCnt; /記錄當(dāng)前篩選出來(lái)的素?cái)?shù)個(gè)數(shù)void sievePrime()int i, j;memset(bp, true, sizeof(bp);bp0 = bp1 = false;for (i = 2; i = Max; i+)if (bpi) /i是素?cái)?shù) ppCnt+ = i; for (j = i * i; j = Max; j += i

12、) /依次篩掉i的倍數(shù)bpj = false;7/23/2022262、線性篩素?cái)?shù) 線性篩素?cái)?shù)算法能夠保證每個(gè)合數(shù)被且僅被其最小素因子篩掉一次。綜觀整個(gè)線性篩素?cái)?shù)的代碼，和普通篩素?cái)?shù)的方法比，只是篩的順序變了。 7/23/202227const int Max = 100;bool bpMax + 1; /記錄每個(gè)數(shù)是否是素?cái)?shù)int p30; /記錄篩選出來(lái)的素?cái)?shù)int pCnt; /記錄當(dāng)前篩選出來(lái)的素?cái)?shù)個(gè)數(shù)void sievePrime()int i, j;memset(bp, true, sizeof(bp);bp0 = bp1 = false;for (i = 2; i = Max;

13、i+)if (bpi) ppCnt+ = i;for (j = 0; j pCnt & i * pj = Max; j+)bpi * pj = false;if (i % pj = 0) break;7/23/202228課后練習(xí)：Number Sequence鏈接地址：Problem Description A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2) mod 7.Given A, B, and n, you are to calculate the value of f(n).Input The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 = A, B = 1000, 1 = n = 100,000,000). Three zeros signal the end of input and this test case