A simple problem 分类：哈希 ...-白红宇

A simple problem 分类：哈希 ...

阅读量：5255 次

发布时间：2019-06-14

本文共 1439 字，大约阅读时间需要 4 分钟。

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

168

Sample Output

0.5

0.3

0.142857

0.005952380

Author

yifenfei

Source

HDU 2008-10 Programming Contest

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

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 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;}