HDU

上题目：

A simple problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2918    Accepted Submission(s): 1041

Problem Description

Zty很痴迷数学问题.。一天，yifenfei出了个数学题想难倒他，让他回答1 / n。但Zty却回答不了^_^. 请大家编程帮助他.

 

Input

第一行整数T，表示测试组数。后面T行，每行一个整数 n (1<=|n|<=10^5).

 

Output

输出1/n. (是循环小数的,只输出第一个循环节).

 

Sample Input

4

2

3

7

168

 

Sample Output

0.5

0.3

0.142857

0.005952380

 

　　中文题意不解释，突然想起小数循环节的问题→_→，找了一条来做做，结果还真的有点问题。首先是题目，1/168=0.005952380,如果正式找循环节为什么不是0595238,但在网上看到其他人说如果真的是0595238的话就得不到1/168了。

　　详细做法看代码，其中f数组是用来保存哪一个余数已经出现过一边，因为同一个余数如果再出现一遍那就说明接下来又得在循环一次了，所以当判断到余数再出现的时候就跳出循环。当前在进入循环之前必须先将f[1]=1,因为可以将起始数当作是最开始的余数。然后每一次余数都要先扩大10倍(就是模拟笔算的过程，被除数不够大就要在后面补零)，然后再进行运算。

 

上代码：

 

#include <cstdio>
#include <cstring>
#define MAX 100002
using namespace std;

bool f[MAX];

int main()
{
    int t,n;
    //freopen("data.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        if(n<0){
            printf("-");
            n=-n;
        }
        if(n==1){
            printf("1
");
            continue;
        }
        printf("0.");
        memset(f,0,sizeof(f));
        int m;
        m=1;
        f[m]=1;
        while(m){
            m=m*10;
            printf("%d",m/n);
            m=m%n;
            if(f[m]) break;
            f[m]=1;
        }
        printf("
");
    }
    return 0;
}