n个1组成的整数能被2013整除c语言,求大神解算法,“编写程序,求n至少为多大时,n个1组成的整数能被2013 整除。”...
編寫程序,求n至少為多大時,n個1組成的整數能被2013 整除。
使用python黑科技:
i = 1
while int('1' * i) % 2013:
i += 1
print(i)
不使用黑科技:
i = s = t = 1
while s % 2013:
i += 1
t = t * 10 % 2013
s = (s + t) % 2013
print(i)
而事實上可以從數論的角度看。
2013=3*11*61
,故:
欲被3整除,n得是3的倍數
欲被11整除,n得是2的倍數
故 n 是 6 的倍數。
而n個1若被 61 整除,則n個9亦然。因為 61 和 10 互素,由費馬小定理知 60 符合條件。故只須嘗試 6,12,30 這三個數即可。
樓上已經有答案了,但私以為沒有解釋的很詳細,因此才有此次回答。
首先,先列下本次回答的題綱:
代碼解法(由于沒有做要求,就用JS實現了)
數論解法(費馬小定理)
代碼解法
function getMinDividedNum(n) {
var sum = 1,
len = 1;
while (sum % n) {
len++;
sum = (sum % n) * 10 + 1;
}
return len;
}
// 測試用例-注意,并不是所有數字都能輸入,只能是素數或者由素數乘積組成的數
var num = 2013;
console.log('n:' + num + ',len:' + getMinDividedNum(num));
//輸出:n:2013,len:60
代碼詳解
以上代碼的核心其實就是判斷
1,11,111
等N位數能否被n整除,也就是
sum=sum*10+1
。
但是考慮到最大值邊界問題,于是將上述公式換為了
sum= (sum % n)*10+1
之所以能這樣轉換,是因為: (舉例)
譬如判斷
111
是否能被3整除
可以是
(1*10+1)*10+1
也可以是判斷
第一步: 1%3=1 (1整除3的余數為1)
第二步: 11%3=2 (11整除3的余數為2)
第三步: 21%3=0 (符合條件)
換一個思路,假如判斷(8+7)是否能被3整除,那么我們只需要現將它們能被3整除的部分去除調,用余數累加起來判斷即可,也就是說只需要判斷
2+1
能否被3整除即可
數論解法
費馬小定理簡介
首先得知道的是,費馬小定理是歐拉定理的一種特殊情況,歐拉定理描述的是關于同余的性質,而費馬定理如下:
假如a是整數,p是質數,且a,p互質(兩者只有一個公約數1),那么a的(p-1)次方除以p的余數恒等于1
即
a^(p-1)%p=1
費馬小定理在本題中的應用
關鍵來了,本題與費馬小定理有什么關系呢?
如上樓中有人提到,本題中,
2013=3*11*61
,所以需要滿足
能被3整除
能被11整除
能被61整除
而前兩者很容易就根據下面的條件判斷出:
若一個整數的數字和能被3整除,則這個整數能被3整除。
若一個整數的奇位數字之和與偶位數字之和的差能被11整除,則這個數能被11整除。
因此馬上就可以將條件轉換為:
n得是3的倍數(因為n個1加起來要是3的倍數)
n得是2的倍數(奇位和偶數直接的差為0)
因此n是6的倍數
n個1這個數(x)能被61整除
接下來就剩下了一個問題: n個1能被61整除,需要滿足什么?接下來費馬小定理就派得上用處了。
我們可以得知: 61和10互素。
所以套用上述的公式,可以得出:
10^(60)%61=1
所以:
10^(60)-1=0 (mod 61)
而
10^60 -1
就是
60個9組成的數
,也就是說 60個9組成的數能夠被61整除。
那么自然60個1組成的數能夠被61整除(因為61與3無關),同時60又是6的倍數,因此滿足條件。
更新,之前有不嚴謹之處
繼續判斷,60的符合條件的約數(6的倍數)有,6,12,30,60。
檢查計算得出后可以知道只有60滿足條件。
因此得出了結論: n至少為60時,n個1組成的數能夠被2013整除
function sum($num,$int=1){
$sum = 0;
foreach (range(0,$num-1) as $key => $value) {
$sum += $int*pow(10,$value);
}
return $sum;
}
$i=1;
while($i++) {
if (sum($i) % 2013 == 0) {
echo $i;//26
break;
}
}
var num = 2013;
var pow = Math.pow;
var floor = Math.floor;
var result = '';
var temp = 0;
var i = 0;
var flag = true;
while(flag){
for (var n = 0; n < 10; n++) {
if ((3 * n + (temp%10)) % 10 === 1) {
result = n + result;
temp = floor((num*result)/pow(10, i + 1));
break;
}
}
if(/1{3,4}/.test(temp.toString())){
flag = false;
}
i++;
}
console.log(result);//55196776508251918087983661754153557432245956836120770547
console.log(result*2013);//1.1111111111111112e+59
跟樓上大神推理的結果一致,60個
總結
以上是生活随笔為你收集整理的n个1组成的整数能被2013整除c语言,求大神解算法,“编写程序,求n至少为多大时,n个1组成的整数能被2013 整除。”...的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: MySQL 笔记6 -- 函数与事务
- 下一篇: 制作 小 linux 教程,【NanoP