NYOJ 330 一个简单的数学

一个简单的数学题

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描写叙述

zyc近期迷上了数学，一天，dj想出了一道数学题来难住他。算出1/n,但zyc一时答不上来希望大家能编程帮助他。

输入

第一行整数T，表示測试组数。

后面T行。每行一个整数 n (1<=|n|<=10^5).

输出

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

例子输入

例子输出

0.5

0.3

0.142857

0.005952380

直接模拟求余数的方法，用一个数组记录商，另外一个数组记录余数是否出现过，假设出现过。说明是第二次循环的開始。在此处跳出循环就可以。

#include<cstdio>

#include<cstring>

const int MAXN = 100005;

int a[MAXN], vis[MAXN];

int main()

{

    int n, t, i;

    scanf("%d",&t);

    while(t--) {

        memset(vis, 0, sizeof(vis));

        scanf("%d",&n);

        if(n < 0) {

            printf("-");

            n = -n;

        }

        if(n == 1) printf("1\n");

        else {

            int s = 1, num = 0;

            vis[s] = 1;

            while(1) {

                s *= 10;

                a[num++] = s / n;

                s %= n;

                if(vis[s] || s == 0) break;  //余数再次出现或者余数为0（即能够整除）

                vis[s] = 1;

            }

            printf("0.");

            for(i = 0; i < num; i++)

                printf("%d", a[i]);

            printf("\n");

        }

    }

    return 0;

}