题目传送门： http://vjudge.net/problem/UVA-202
题意：除法模拟，循环小数要将循环位表示出来。
思路：此题的关键是找到循环节，循环节可以可以根据模拟除法时没次的余数进行判断，若出现之前重复的余数，说明出现了循环节，回溯找到完整的循环节，然后输出就行了。
代码如下：
#include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; #define lowbit(x) x&(-x) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ll long long #define ull unsigned long long #define mem(n,v) memset(n,v,sizeof(n)) #define MAX 1000005 #define MAXN 2000005 #define PI 3.1415926 #define E 2.718281828459 #define opnin freopen("text.in.txt","r",stdin) #define clsin fclose(stdin) const int INF = 0x3f3f3f3f; const ll INFF = 0x3f3f; const double pi = 3.141592653589793; const double inf = 1e18; const double eps = 1e-8; const ll mod = 1e9+7; const ull mx = 133333331; struct digit { int num; bool flag; int last; bool posi;//true >0 digit(int n= 0,int l = 0,int f = 0,int p = 0) : num(n),last(l),flag(f),posi(p){} }; struct digit digits[MAX]; int ans[MAX]; int ans1[MAX]; void init() { mem(digits,0); mem(ans,0); mem(ans1,0); } int main() { int a,b; while(scanf("%d %d",&a,&b) != EOF){ init(); printf("%d/%d = ",a,b); int temp = a/b; a %= b; if(a == 0 && temp == 0){ printf("0.(0)\n 1 = number of digits in repeating cycle\n\n"); continue; } int be = a; digits[a].flag = 1; digits[a].num = temp; digits[a].posi = true; int last = a; // cout << "a,num: " << a << ' ' << temp << endl; for(;;){ a *= 10; temp = a/b; a %= b; // cout << "a,num: " << a << ' ' << temp << endl; if(digits[a].flag) break; digits[a].flag = 1; digits[a].num = temp; digits[a].posi = false; digits[a].last = last; last = a; } int f = a; int b = last; int cnt = 0; int cnt2 = 0; int cnt3 = 0; bool flag = false; if(!a) ans[cnt++] = 0; else{ ans[cnt++] = temp; while(b != a){ ans[cnt++] = digits[b].num; b = digits[b].last; } } while(!digits[b].posi){ ans1[cnt2++] = digits[b].num; b = digits[b].last; } printf("%d.",digits[be].num); for(int i=cnt2-1;i>=0;i--){ printf("%d",ans1[i]); if(++cnt3 == 50){ flag = true; break; } } if(!flag){ printf("("); for(int i=cnt-1;i>=0;i--){ printf("%d",ans[i]); if(++cnt3 == 50){ printf("..."); break; } } printf(")"); } printf("\n %d = number of digits in repeating cycle\n",cnt); printf("\n"); } return 0; }