P1530 分数化小数 Fractions to Decimals【洛谷算法习题】

P1530 分数化小数 Fractions to Decimals网页链接P1530 分数化小数 Fractions to Decimals题目描述写一个程序输入一个形如N D \dfrac{N}{D}DN​的分数输出它的小数形式。如果小数有循环节的话把循环节放在一对圆括号中。例如1 3 0.33333333 … \dfrac{1}{3}0.33333333\ldots31​0.33333333…写成0. ( 3 ) 0.(3)0.(3)41 333 0.123123123 … \dfrac{41}{333} 0.123123123\ldots33341​0.123123123…写成0. ( 123 ) 0.(123)0.(123)整数x xx写成x .0 x.0x.0。输入格式输入包含两个整数N NN和D DD1 ≤ N , D ≤ 10 5 1 \leq N,D \leq 10^51≤N,D≤105。输出格式输出按照上面规则计算出的小数表达式。如果结果长度大于76 7676每行输出76 7676个字符。输入输出样例 #1输入 #145 56输出 #10.803(571428)说明/提示翻译来自NOCOWUSACO 2.4解题思路本题是模拟长除法 循环节检测的经典题型核心是通过记录每次除法后的余数来定位循环节的起点和长度并按要求格式化输出。1. 问题等价转化分数转小数整数部分为⌊ N / D ⌋ \lfloor N/D \rfloor⌊N/D⌋若整除则补.0。小数部分通过不断将余数乘10 1010后除以D DD获得每一位。有限与循环若分母D DD的所有质因子只包含2 22和5 55则小数有限直接除尽即可。否则为无限循环小数循环节从某次出现重复余数时开始。循环节定位在模拟除法时用数组bk[x]记录余数x xx实际上是当前被除数n nn即上一轮余数乘10 1010首次出现的位置已输出的小数位数。当同一个被除数再次出现时两次出现之间的部分即为一个循环节。2. 算法实现预处理与输出整数部分计算q N / D输出q.。若N % D 0补0后直接结束。初始化计数器v已输出字符数用于控制每行76 7676字符的换行。判断有限小数将D DD反复除以2 22和5 55若最终变为1 11则小数有限。有限情况下模拟除法直接逐位输出直到余数为0 00无需括号。无限循环小数处理模拟长除法每次n (n % d) * 10商digit n / d保存到数组a用bk[n]记录当前商的位置z。若某个n已经记录过说明循环开始循环节起点flag bk[n]。输出时在位置flag前输出(然后依次输出a[1..z]最后补)。其间通过v累计字符数每76 7676个字符输出一次换行。注意整数部分和小数点也计入总长度开头输出q.时已累加相应字符数。3. 复杂度分析时间复杂度每位小数一次除法最长循环节不超过D DD余数最多D DD种D ≤ 10 5 D \le 10^5D≤105总时间O ( D ) O(D)O(D)非常快。空间复杂度O ( D ) O(D)O(D)用于记录余数首次出现位置的数组10 5 10^5105规模完全可行。总结模拟手动长除法的过程利用余数判重找到循环节。有限小数直接输出无限小数精确标记循环起止并添加括号。特别需要注意输出格式每行不超过76 7676个字符。代码简要说明读入与整数部分输出用scanf读取N , D N, DN,Dprintf输出整数部分和小数点并初始化字符计数v。有限小数判断提取D DD中所有2 22和5 55因子若剩余为1 11则进入有限分支直接逐位输出。无限循环小数记录初始化bk数组全0 00z记录已存小数位数。当bk[(n % d) * 10]为空时计算商存入a[z]标记bk[当前被除数] z。一旦发现重复记录循环起点flag。格式化输出遍历i从1 11到z在i flag时输出(并更新计数v。每输出一个数字检查(i v) % 76 0则换行。最后输出)并换行。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,d,z0,flag,v,a[110000],bk[1100000];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,d);printf(%lld.,n/d);if(n%d0){printf(0);return0;}ll td;while(t%50)t/5;while(t%20)t/2;if(t1){while(n%d!0){n(n%d)*10;printf(%lld,n/d);}}else{ll qn/d;v;if(!q)v;while(q){q/10;v;}while(!bk[(n%d)*10]){n(n%d)*10;a[z]n/d;bk[n]z;}flagbk[(n%d)*10];for(ll i1;iz;i){if(iflag){printf(();v;}printf(%lld,a[i]);if((iv)%760)printf(\n);}printf()\n);}return0;}