題目
L1-6 整除光棍 (20 分)
這里所謂的“光棍”，并不是指單身汪啦~ 說(shuō)的是全部由1組成的數(shù)字只恨，比如1译仗、11、111官觅、1111等纵菌。傳說(shuō)任何一個(gè)光棍都能被一個(gè)不以5結(jié)尾的奇數(shù)整除。比如休涤，111111就可以被13整除咱圆。 現(xiàn)在，你的程序要讀入一個(gè)整數(shù)x功氨，這個(gè)整數(shù)一定是奇數(shù)并且不以5結(jié)尾序苏。然后，經(jīng)過(guò)計(jì)算捷凄，輸出兩個(gè)數(shù)字：第一個(gè)數(shù)字s忱详，表示x乘以s是一個(gè)光棍，第二個(gè)數(shù)字n是這個(gè)光棍的位數(shù)纵势。這樣的解當(dāng)然不是唯一的,題目要求你輸出最小的解踱阿。
提示：一個(gè)顯然的辦法是逐漸增加光棍的位數(shù)，直到可以整除x為止钦铁。但難點(diǎn)在于软舌，s可能是個(gè)非常大的數(shù) —— 比如，程序輸入31牛曹，那么就輸出3584229390681和15佛点，因?yàn)?1乘以3584229390681的結(jié)果是111111111111111，一共15個(gè)1黎比。
輸入格式：
輸入在一行中給出一個(gè)不以5結(jié)尾的正奇數(shù)x（<1000）超营。
輸出格式：
在一行中輸出相應(yīng)的最小的s和n，其間以1個(gè)空格分隔阅虫。
根據(jù)題目提示演闭，僅僅通過(guò)longlong等數(shù)據(jù)類型裝是不夠的，大整數(shù)除法要用到 數(shù)組來(lái)裝
原理：
以12345 / 8 ≈ 1543為例：
- 1與7比較颓帝， 不夠除米碰， 因此該位商為 0, 余數(shù)為1窝革。
- 余數(shù)1與新位 2組合成12, 12與8比較， 夠除吕座， 商為1, 余數(shù)為4虐译。
- 余數(shù) 4與新位 3組合成 43, 43與 8 比較， 夠除吴趴， 商為 5, 余數(shù)為3 漆诽。
- 余數(shù) 3與新位 4組合成 34, 34與 8 比較， 夠除锣枝， 商為 4, 余數(shù)為 2厢拭。
- 余數(shù) 2 與新位 5 組合成 25, 25與8比較，夠除惊橱，商為3蚪腐，余數(shù)為1。
- 沒(méi)有新位了税朴。
上一步的余數(shù)乘以10加上該步的位， 得到該步臨時(shí)的被除數(shù)家制，
將其與除數(shù)比較： 如果不夠除正林， 則該位的商為 0: 如果夠除， 則商即為對(duì)應(yīng)的商颤殴， 余數(shù)即為對(duì)應(yīng)的余數(shù)觅廓。 最后一步要注意減法后高位可能有多余的O, 要忽視它們， 但也要保證結(jié)果至少有一位數(shù)涵但。
代碼：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[1000]={0};//初始化
int n;
cin>>n;
for(int i=0;;i++){//沒(méi)找到適合的光棍數(shù)時(shí)會(huì)一直加1
a[i]=1;
int ans[1000];//裝答案
int d=0;
for(int j=0;j<=i;j++){
d=d*10+a[j];//該步臨時(shí)的被除數(shù)
ans[j]=d/n;//得出答案該位的數(shù)
d=d%n;//余數(shù)
}
if(d!=0) continue;//還未找到答案 繼續(xù)尋找
//到達(dá)這里說(shuō)明找到了
int j=0;
while(ans[j]==0&&j<=i) j++;//前面的0記得先拿掉
for(int k=j;k<=i;k++) {
cout<<ans[k];
}
cout<<" "<<i+1;//此時(shí)i+1便是位數(shù)
return 0;
}
return 0;
}
