L1-6 整除光棍(20 分)
這裡所謂的“光棍”,并不是指單身汪啦~ 說的是全部由1組成的數字,比如1、11、111、1111等。傳說任何一個光棍都能被一個不以5結尾的奇數整除。比如,111111就可以被13整除。 現在,你的程式要讀入一個整數
x
,這個整數一定是奇數并且不以5結尾。然後,經過計算,輸出兩個數字:第一個數字
s
,表示
x
乘以
s
是一個光棍,第二個數字
n
是這個光棍的位數。這樣的解當然不是唯一的,題目要求你輸出最小的解。
提示:一個顯然的辦法是逐漸增加光棍的位數,直到可以整除
x
為止。但難點在于,
s
可能是個非常大的數 —— 比如,程式輸入31,那麼就輸出3584229390681和15,因為31乘以3584229390681的結果是111111111111111,一共15個1。
輸入格式:
輸入在一行中給出一個不以5結尾的正奇數
x
(<1000)。
輸出格式:
在一行中輸出相應的最小的
s
和
n
,其間以1個空格分隔。
輸入樣例:
31
輸出樣例:
3584229390681 15
大神連結: 大神分析
大神的高精度算法
#include <bits/stdc++.h>
using namespace std;
int x, k = 0, ans[1000000];
string s;
bool cal()
{
int t = 0;
k = 0;
for(int i = 0; i < s.size(); i++){
t = t * 10 + s[i] - '0';
if(k || t >= x)//就是這,我一開始是t>=x是以導緻一直沒拿全分數
{
ans[k++] = t / x;
t %= x;
}
}
if(t == 0)
return 0;
return 1;
}
int main()
{
cin >> x;
s = "1";
while(cal())
s += "1";
for(int i = 0; i < k; i++)
cout << ans[i];
cout << " " << s.size() << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;// 我的模仿
string s;
int ans[2000005];
int t,x;
int num;
bool check(){
ans[num++] = t/x;
if (t < x)return true;
t = t%x;
if(t==0) return false;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin >> x;
s = "1";
t = 1;
while (check()){
s += "1";
t = t*10+1;
}
int i;
for (i = 0;i < num;i ++){
if (ans[i] != 0)break;
}
for (;i < num;i ++)
cout << ans[i];
cout << ' ' << s.size() << endl;
}
哇,還有一個方法
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int flag = 0;
int i;
int x = 0;
for(i = 1;; i ++)
{
x = x*10 + 1;
if (x >= n){
flag = 1;
cout << x/n;
}
else if (flag)
{
cout << 0;
}
x = x%n;
if(x == 0) break;
}
cout << " " << i <<endl;
// cout << "Hello world!" << endl;
return 0;
}