A simple problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3702 Accepted Submission(s): 1383

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

Author

yifenfei

Source

HDU 2008-10 Programming Contest

一道有意思的题,哈希思想,不过在初始化的时候有点小技巧可以防止超时.

#include <map>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

#define eps 1e-9

#define LL long long

#define PI acos(-1.0)

#define INF 0x3f3f3f3f

#define CRR fclose(stdin)

#define CWW fclose(stdout)

#define RR freopen("input.txt","r",stdin)

#pragma comment(linker, "/STACK:102400000")

#define WW freopen("output.txt","w",stdout)

const int MAX = 1e5+10;

bool vis[MAX*10];

int main()

{

    int T;

    int n,m;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        if(n<0)

        {

            printf("-");

            n=-n;

        }

        if(n==1)

        {

            printf("1");

        }

        else

        {

            printf("0.");

            memset(vis,false,(n*10)*sizeof(vis[0]));//不必全部初始化

            m=10;

            vis[10]=true;

            while(1)

            {

                printf("%d",m/n);

                vis[m]=true;

                m=m%n;

                if(m==0)

                {

                    break;

                }

                m*=10;

                if(vis[m])

                {

                    break;

                }

            }

        }

        printf("\n");

    }

    return 0;

}

版权声明：本文为博主原创文章，未经博主允许不得转载。