國家集訓(xùn)隊(duì)作業(yè)神秘?cái)?shù)報(bào)告

1、神秘?cái)?shù)摘 要算法：邏輯推理判斷空間復(fù)雜度：O(N2)時(shí)間復(fù)雜度：遠(yuǎn)小于O(N3)問 題 大 意有兩個(gè)自然數(shù) a1，b1，且不相等，M 先生知道兩個(gè)數(shù)的乘積 M,S 先生知道兩個(gè)數(shù)的和S?，F(xiàn)在兩人有如下（1）M 先生：我不知道這兩個(gè)數(shù)；：（2）S 先生：我不知道這兩個(gè)數(shù)，但我知道你也不知道；（3）M 先生：現(xiàn)在我知道是哪兩個(gè)數(shù)了；（4）S 先生：現(xiàn)在我也知道了。給出一個(gè)范圍x=ab=y,求此范圍內(nèi)所有滿足題目條件的(a,b)。算 法 分 析這道題通過 4 句話給出了大量的信息。分析第一句話：M 先生不能確定這兩個(gè)數(shù)。所以 M 不是兩個(gè)質(zhì)數(shù)的乘積。分析第二句話：S 先生不能確定這兩個(gè)數(shù)，因此將S

2、分解為兩數(shù)和有多種方案。同時(shí)S 能肯定M 不知道，即S 不能分解為兩個(gè)質(zhì)數(shù)的和。分析第三句話：將M 分解為兩個(gè)數(shù)的乘積，這些分解方案為 X=(a,b)|a*b=M,則X 集合中應(yīng)該有且僅有一對(a,b),a+b 滿足第二句話。分析第四句話：S 現(xiàn)在也得知這兩個(gè)數(shù)。將 S 分解為兩個(gè)數(shù)的和， 這些分解方案為X=(a,b)|a+b=M,則 X 集合中應(yīng)該有且僅有一對(a,b),a*b 滿足第三句話。這僅有的一對(a,b)就是符合題目推理的。算 法 的 實(shí) 現(xiàn)根據(jù)以上分析，通過枚舉兩個(gè)數(shù)的和，來找到所有范圍內(nèi)的解。因?yàn)椴豢赡苡袃山M解的和都為同一個(gè)S。根據(jù)條件 4，將 S 分解，驗(yàn)證第 3 個(gè)條件。驗(yàn)

3、證第 3 個(gè)條件時(shí)還要用到前面兩個(gè)條件。前兩個(gè)條件，根據(jù)哥德巴赫猜想，應(yīng)該滿足S 大于 6 的奇數(shù)，且S-2 不是質(zhì)數(shù)。如果S 是偶數(shù)，則它是一個(gè)合數(shù)，一定可以分解為兩質(zhì)數(shù)的和。判斷M 是否滿足第三個(gè)條件，即將給定 M 分解，只有一對滿足前兩個(gè)條件。判斷S 是否滿足第四個(gè)條件，即將給定S 分解，只有一對滿足前三個(gè)條件，且這一對數(shù)就是一組。具體的過程見程序。實(shí)現(xiàn)時(shí)用得最多的是前兩個(gè)條件，為了方便質(zhì)數(shù)的判斷，先做一個(gè)質(zhì)數(shù)表。算法的時(shí)間復(fù)雜度按分析是 N 的 3 次方的，實(shí)際上由于算法實(shí)現(xiàn)是自頂向下，只有必要時(shí)才進(jìn)行計(jì)算，所以實(shí)際計(jì)算次數(shù)很少。要求的規(guī)模，即兩個(gè)數(shù)小于 550，可以瞬間求出全部的 2

4、2 組解。對于問題#include #include#includeconstUPMOST=550*550;/兩數(shù)乘積的最大可能值bool primeUPMOST;void computePrimes()i,j; memset(prime,1,sizeof(prime); for (i=2;iUPMOST;i+)/預(yù)計(jì)算所有的素?cái)?shù)if(primei)for (j=i+i;j7&sum%2&!primesum-2);fitcondition3(m)/檢驗(yàn)積 m 是否滿足前三個(gè)條件t=0;i,j;for (i=(sqrt(m);i=2;i-)if (m%i=0)j=m/i; if (i1)break; /檢查是否唯一滿足returnt=1;/如果唯一滿足，則 m 滿足第 3 個(gè)條件void main()x,y; cinxy; computePrimes();for(s = x+x+1;s=y+y+1;s+=2)/枚舉所有可能的和，判斷是否僅有一對分解滿足條件if(fittwo(s)/首先要滿足前兩個(gè)條件t= 0;ansa,ansb;for (a = 2;a1) break; /不符合唯一滿足，跳出檢查if (a