亿阳信通：不可表示的数
前些日子在網(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数据类型
- 下一篇： 计算机小高考要点,小高考的复习计划