亿阳信通:不可表示的数
前些日子在網(wǎng)上發(fā)現(xiàn)一道編程題目,引用如下:
題目詳情:
本題的獎(jiǎng)品由億陽(yáng)信通贊助,以下是題目詳情:
給定表達(dá)式[x/2] + y + x * y, 其中x,y都是正整數(shù)。其中的中括號(hào)表示下取整,例如[3/2] = 1 , [5/2] ?= 2。
有些正整數(shù)可以用上述表達(dá)式表達(dá)出來(lái),例如正整數(shù)2,當(dāng)取x = y = 1時(shí),可以把2表達(dá)出來(lái)
( 解釋下:當(dāng)x=y=1時(shí), [x / 2] + y + x * y = [1 / 2] + 1 + 1 * 1 = 0+1+1 = 2 );
有些數(shù)可以有多種方式表達(dá),例如13可以由 x = 2 y = 4 以及x = 3 y = 3來(lái)表示;
有些數(shù)無(wú)法用這個(gè)表達(dá)式表達(dá)出來(lái),比如3。
從1開始第n個(gè)不能用這個(gè)表達(dá)式表示出來(lái)的數(shù),我們叫做an,例如a1=1 a2=3,給定n,求an。
輸入:n值 1<=n<=40
輸出:an % 1000000007的結(jié)果(因?yàn)榻Y(jié)果較大,輸出an %1000000007的結(jié)果)。
函數(shù)頭部
C/C++:
int givean(int n);
java:
public class Main {
? ? ? public static int givean(int n) {
? ? }
}
答題說(shuō)明:
main函數(shù)可以不用完成,完成givean函數(shù)即可,givean函數(shù)外可編寫其它函數(shù)。
一時(shí)興起,就嘗試解答此題,思路:使用二重循環(huán)窮舉法來(lái)判斷一個(gè)數(shù)是不是不可表示的數(shù)。
我的代碼:
public static int givean(int n){if (n < 1 || n > 40){return -1;}long i = 0;while (n > 0){i++;if (isUndisplayNumber(i)){n--;}}return (int) (i % 1000000007);}/*** 判斷n是否為不可表示數(shù)* * @param n* @return*/private static boolean isUndisplayNumber(long n){if (n == 1 || n == 3){return true;} else if (n % 2 == 0){return false;}for (long i = 1; i <= n; i++){for (long j = 1; j <= n; j++){long m = i / 2 + j + i * j;if (m > n){break;}if (m == n){return false;}}}return true;}編譯和測(cè)試結(jié)果顯示正常(其實(shí)givean(6)運(yùn)行已經(jīng)超時(shí),超過(guò)100s),提交結(jié)果:
【抱歉,處理您的請(qǐng)求時(shí)出錯(cuò)。】
知道這是因?yàn)槲业母F舉法太費(fèi)時(shí)了,嘗試了幾種優(yōu)化方案,但效果都不明顯。在此標(biāo)記,以備后學(xué)!
=========================================================================================================================
備注:
后來(lái)利用搜索引擎在開心問(wèn)答網(wǎng)上搜到一篇相關(guān)文章(http://www.kaixinwenda.com/article-lzc52151-9957839.html),分析如下:
推導(dǎo):
1、? 對(duì)[x/2] + y + x * y分析,試探:x=1,原式=2y,表示所有偶數(shù),即對(duì)所有偶數(shù)都能用此式表示,故后文重點(diǎn)討論哪些奇數(shù)不能被其表示(本文討論的所有奇偶數(shù)都為非負(fù)數(shù))。
2、? 對(duì)x分為4n,4n+1,4n+2,4n+3四種情況討論。
容易得到,x=4n+1時(shí),不論y取何值,原式必為偶數(shù),與1)中情況重復(fù),故舍去不討論;
x=4n時(shí),y=2m+1才能保證原式為奇數(shù),其中要保證n>0;
x=4n+2時(shí),y=2m才能保證原式為奇數(shù),其中要保證m>0;
x=4n+3時(shí),y=2m或2m+1都能使原式為奇數(shù);
故只討論后三種情況。
3、? 把x=4n,y=2m+1代入原式易得2(m+n)+8mn+4n+1、n>0;
把x=4n+2,y=2m代入原式易得2(m+n)+8mn+4m+1、m>0;
明顯,這兩種情況可表示的奇數(shù)是相同的,故只需研究其中一種即可。
總結(jié)一下,目前已知原式對(duì)所有偶數(shù)可表示,對(duì)哪些奇數(shù)可表示呢?我們要研究的情況只有兩種x=4n+2(即x=4n)與x=4n+3時(shí)的情況。
4、? 對(duì)x=4n+2時(shí),不限制y的奇偶性,此情況下,原式可表示為2n+3y+4ny+1;
對(duì)x=4n+3時(shí),不限制y的奇偶性,,此情況下,原式可表示為2n+4y+4ny+1;
下面我們重點(diǎn)討論這兩種情況表示的奇數(shù)包括哪些。
5、? 對(duì)x=4n+3,原式=2n+4y+4ny+1=2(n+1)(2y+1)-1,即表示一個(gè)奇數(shù)(2y+1)的偶數(shù)倍減1。也就是說(shuō)x=4n+3情況時(shí),表示的奇數(shù)都具備一個(gè)特征:這個(gè)奇數(shù)可以寫成一個(gè)奇數(shù)的偶數(shù)倍減1。
故我們可以得到下面的結(jié)論:在x=4n+3的情況下,如果偶數(shù)B能寫成一個(gè)奇數(shù)的偶數(shù)倍,即奇數(shù)與偶數(shù)的乘積,那么奇數(shù)A=B-1可以被原式表示。
其逆否命題:在x=4n+3的情況下,奇數(shù)A=B-1不可以被原式表示,則偶數(shù)B不能寫成奇數(shù)與偶數(shù)的乘積,即其因子分解只能寫成偶數(shù)與偶數(shù)的乘積。
一個(gè)偶數(shù)因子分解只能寫成偶數(shù)與偶數(shù),只有2的冪了。
故得到結(jié)論:在x=4n+3的情況下,不可以被原式表示的奇數(shù)都是2的冪減1。
6、? 對(duì)x=4n+2,原式=2n+3y+4ny+1=[(4n+3)(2m+1)-1]/2,即表示兩個(gè)奇數(shù)的積減1的差的一半。也就是說(shuō)x=4n+2情況時(shí),表示的奇數(shù)都具備一個(gè)特征:這個(gè)奇數(shù)可以寫成兩個(gè)奇數(shù)的積(4n+3)(2m+1)減1的差的一半。
換句話說(shuō),在x=4n+2的情況下,原式所能表示的奇數(shù)A都可以寫成兩個(gè)奇數(shù)的積減1的差的一半。反過(guò)來(lái),2A+1必定能寫成兩個(gè)奇數(shù)的積。
而對(duì)任意的2A+1必為奇數(shù),它要么能寫成兩個(gè)奇數(shù)的積要么是素?cái)?shù)。
故得到結(jié)論:在x=4n+2的情況下,不可以被原式表示的奇數(shù)A都是某個(gè)素?cái)?shù)減1的差的一半。
7、? 把1)、5)與6)的結(jié)論綜合起來(lái),對(duì)任意正整數(shù)x、y,如果不能被原式表示,它必定是奇數(shù),這個(gè)奇數(shù)必定是2的冪減1,同時(shí)是某個(gè)素?cái)?shù)減1的差的一半。
用形式化語(yǔ)言表達(dá),對(duì)任意正整數(shù)x、y,不能被[x/2] + y + x * y表示的數(shù),必定可以寫成2^p-1,且2^(p+1)-1是一個(gè)素?cái)?shù)。
8、? 于是我們得到這個(gè)問(wèn)題的解答:an中的元素都滿足2^p-1且2^(p+1)-1是素?cái)?shù)。
--------------------------------------------------------------------------------------
編程求解:
問(wèn)題從數(shù)學(xué)上已經(jīng)解決了,并得到了一個(gè)漂亮的解答。但如何求2^p-1,還要判斷2^(p+1)-1是否為素?cái)?shù),這都是非常困難。
一步步來(lái),求素?cái)?shù),傳統(tǒng)方法當(dāng)然是素性檢測(cè),以前寫過(guò)一個(gè)拉賓米勒測(cè)試,很復(fù)雜。但突然意識(shí)到對(duì)2^p-1如果是素?cái)?shù)的話,數(shù)論被叫做梅森素?cái)?shù),前人肯定有總結(jié)。
百度一下,前40個(gè)梅森素?cái)?shù)的冪指數(shù)(p+1)取值為:2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213,19937,21701,23209,44497,86243,110503,132049,216091,756839,859433,1257787,1398269,2976221,3021377,6972593,13466917,20996011。
有了梅森素?cái)?shù),只要求相應(yīng)的2^p-1即可。素?cái)?shù)的問(wèn)題是解決了,但2^20996011是個(gè)什么概念,天文數(shù)字,再?gòu)?qiáng)大計(jì)算機(jī)一時(shí)半會(huì)兒也算不出來(lái)。幸好題目是拿an對(duì)1000000007取模。通過(guò)模運(yùn)算可以簡(jiǎn)化問(wèn)題。
模運(yùn)算(2^p-1)%N=(2^p%N-1)%N,在這里等于2^p%N-1。但下面一個(gè)問(wèn)題來(lái)了2^p%N怎么求?
2^p%N是一個(gè)龐大的數(shù),傳統(tǒng)的方法是遞歸,無(wú)論從空間還是時(shí)間上來(lái)說(shuō)都不解決問(wèn)題。幸好往日有積累,對(duì)這種變態(tài)需求,當(dāng)然有特殊手段。運(yùn)用蒙哥馬利算法可以迅速解決,秒殺之。
最后得到an的前40個(gè)數(shù):1,3,15,63,4095,65535,262143,73741816,536396503,140130950,487761805,319908070,106681874,373391776,317758023,191994803,416292236,110940209,599412198,383601260,910358878,532737550,348927936,923450985,470083777,642578561,428308066,485739298,419990027,287292016,202484167,389339971,848994100,273206869,853092282,411696552,876153853,90046024,828945523,697988359。
提交代碼的時(shí)候,寫成枚舉,成功!
總結(jié)
以上是生活随笔為你收集整理的亿阳信通:不可表示的数的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: java 定义char_JAVA数据类型
- 下一篇: 计算机小高考要点,小高考的复习计划