题解 P1530 【分数化小数 Fractions to Decimals】

# 这题时珍的皮！ 如同楼下的说法，是用长除法来做，然而我并不知道长除法的做法233，于是就想了很久算法。由于我不会**哈希算法**，所以我用了结构体来标记已经保留过的余数。还有要注意的是输出时要判断76个字符一行，所以我自己加了个函数来换行hh ···cpp ```cpp #include<cstdio> struct node{ int f,cr; }mark[1000010]; int ans[1000010];//记录要输出的ans int flag,len,point,k,kx,st[20]; void xo(int c){ kx++; if (kx==77){//每输出76个字符换一行 kx=1; puts(""); } putchar(c); } void xout(int k){//输出优化 int num=0; if (k<0) xo(45),k=-k; while (k) st[++num]=k%10,k/=10; if (num!=0) while (num) xo(st[num--]+48); else xo(48); } int main(){ int n,d; scanf("%d%d",&n,&d);//输入 xout(n/d); xo('.');//输出整数部分和小数点 if (n%d==0){ xo(48); return 0; ``` }//如果n被d整除就输出0结束 ```cpp n=n%d; while (n!=0){//当n等于0时输出结果 n*=10;//将上次计算得的余数乘10像长除法一样计算 if (mark[n].f){//如果n已经出现过，就是出现了循环节，所以直接输出 for (int i=1;i<mark[n].cr;i++) xo(ans[i]+48); xo('('); for (int i=mark[n].cr;i<=len;i++) xo(ans[i]+48); xo(')'); return 0; ``` }//注意输出的格式 ```cpp ans[++len]=n/d; mark[n].f=1; mark[n].cr=len; n=n%d;//标记n以及n出现的位置，标记结果，n更新为n被d除的余数 } for (int i=1;i<=len;i++) xo(ans[i]+48);//最后输出 return 0; } ··· ```