Fractions to Decimals_usaco2.4.5_暴力

NO IMAGE

題目描述 Description


寫一個程式,輸入一個形如 N/D 的分數(N 是分子,D 是分母),輸出它的小數形式。
如果小數有迴圈節的話,把迴圈節放在一對圓括號中。例如,
1/3 = .33333333 寫成 0.(3)
41/333 = 0.123123123… 寫成 0.(123)
用 xxx.0 成表示整數
典型的轉化例子:
1/3 = 0.(3)
22/5 = 4.4
1/7 = 0.(142857)
2/2 = 1.0
3/8 = 0.375
45/56 = 0.803(571428)

輸入描述 Input Description


一行兩個整數N和D

他們均大於0小於100 000

輸出描述 Output Description


如描述所說的那樣。

如果轉化出的長度超過76個字元,每行輸出76個

題解 Analysis


換回win10不爽不爽不爽(┬_┬)
舉幾個例子可以發現,有迴圈節的小數在作除法過程中會出現重複的餘數
於是就愉快地用桶記錄一下,然後模擬除法往後算
輸出坑得一B,不過只要保證最後只有一個換行就可以了
每行七十六個輸出也是微醺,無力吐槽

程式 Code


/*
ID:wjp13241
PROG:fracdec
LANG:C  
*/
#include <stdio.h>
#include <queue>
using namespace std;
struct frac
{
int mr,dr;
};
queue<frac>q;
int t[100001];
int main()
{
freopen("fracdec.in","r",stdin);
freopen("fracdec.out","w",stdout);
int a,b,st,ed,v=1,cnt=0;
scanf("%d%d",&a,&b);
printf("%d.",a/b);
q.push((frac){a,b});
while (q.size())
{
frac now=q.front();q.pop();
int tmp=now.mr%now.dr;
if (!t[tmp])
{
q.push((frac){tmp*10,now.dr});
t[tmp]=  cnt;
}
else
{
st=t[tmp];
ed=cnt-st;
break;
}
}
int tmp=a/b;
do{v  ;}while (tmp/=10);
a%=b;
if (!a)
printf("0");
while (--st)
{
printf("%d",a*10/b);
a=a*10%b;
v%=76;
if (!v)
printf("\n");
}
if (a)
{
printf("(");
v%=76;
if (!v)
printf("\n");
while (ed--)
{
printf("%d",a*10/b);
a=a*10%b;
v%=76;
if (!v)
printf("\n");
}
printf("%d)",a*10/b);
}
printf("\n");
return 0;
}