Luogu P1530 分数化小数 Fractions to Decimals(模拟)

P1530 分数化小数 Fractions to Decimals

题意

题目描述

写一个程序，输入一个形如\(N/D\)的分数(\(N\)是分子，\(D\)是分母)，输出它的小数形式。如果小数有循环节的话，把循环节放在一对圆括号中。

例如,\(1/3=0.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)
PROGRAM NAME fracdec


输入输出格式

输入格式：

单独的一行包括被空格分开的\(N\)和\(D(1 \leq N,D \leq 100000)\)。

输出格式：

按照上面规则计算出的小数表达式.如果结果长度大于\(76\),每行输出\(76\)个字符.

输入输出样例

输入样例：

45 56


输出样例：

0.803(571428)


说明

USACO 2.4

思路

来，\(solo\)！P1530。 --alecli & Mercury

来咧。 --Uranus

换题了换题了。 --alecli & Mercury & Uranus

昨天晚上的\(solo\)水题，但是巨佬们都不做了，只有我写了\(qwq\)。

实际上思路是很简单的，首先处理小数点左边的数字，直接取\(\lfloor n/d \rfloor\)就好了。然后我们用竖式除法的方式来模拟处理循环节，对于每一位上的运算，假设当前算出来结果是\(a\)，余数为\(b\)，我们就查找前面的运算过程中有没有结果是\(a\)且余数为\(b\)的，如果有，循环节就找到了。当然我们还要处理整除的情况，这就只需要判断\(b=0\)是否为真。

具体来说我们可以这么写：

while(n!=0)//循环利用n来做b
{
n*=10;//计算下一位
tmp=n/d;//这一位上的计算结果a
n-=tmp*d;//余数b
bool found=false;//打标记看能不能找到循环节
for(int i=0;i<G[tmp].size();i++)//G是一个vector，里面储存的是pair<int,int>，first储存余数，second储存出现的位置
if(G[tmp][i].first==n)//找到了
{
found=true;//修改标记
int now=G[tmp][i].second;//找到位置
string re;//处理新字符串（之前的运算结果都储存在字符串ans中）
for(int j=0;j<now;j++) re+=ans[j];//处理循环节之前的
re+='(';//循环节开始
for(int j=now;j<ans.length();j++) re+=ans[j];//处理循环节内部的
re+=')';//循环节结束
ans=re;//更新答案
break;//溜了溜了
}
if(found) break;//找到了，溜了溜了
ans+=(tmp+'0');//更新答案
G[tmp].push_back(make_pair(n,ans.length()-1));//更新vector
}


再处理好一些细节，就能\(AC\)了。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int n,d;
vector<PII>G[10];
string ans;
int read()
{
int re=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
return re;
}
string to_str(int x)
{
if(!x) return "";
string re=to_str(x/10);
re+=(x%10+'0');
return re;
}
int main()
{
cin>>n>>d;
int tmp=n/d;
n-=tmp*d;
ans+=to_str(tmp);
if(!ans.length()) ans+='0';
ans+='.';
while(n!=0)
{
n*=10;
tmp=n/d;
n-=tmp*d;
bool found=false;
for(int i=0;i<G[tmp].size();i++)
if(G[tmp][i].first==n)
{
found=true;
int now=G[tmp][i].second;
string re;
for(int j=0;j<now;j++) re+=ans[j];
re+='(';
for(int j=now;j<ans.length();j++) re+=ans[j];
re+=')';
ans=re;
break;
}
if(found) break;
ans+=(tmp+'0');
G[tmp].push_back(make_pair(n,ans.length()-1));
}
if(ans[ans.length()-1]=='.') ans+='0';
for(int i=0;i<ans.length();i++)
{
putchar(ans[i]);
if(i%76==75) puts("");
}
return 0;
}