HDU 5752

Sqrt Bo

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 423 Accepted Submission(s): 188

Problem Description

Let's define the function $f(n)=lfloor sqrt{n} floor$.

Bo wanted to know the minimum number $y$ which satisfies $f^y(n)=1$.

note:$f^1(n)=f(n),f^y(n)=f(f^{y-1}(n))$

It is a pity that Bo can only use 1 unit of time to calculate this function each time.

And Bo is impatient, he cannot stand waiting for longer than 5 units of time.

So Bo wants to know if he can solve this problem in 5 units of time.

Input

This problem has multi test cases(no more than $120$).

Each test case contains a non-negative integer $n(n<10^{100})$.

Output

For each test case print a integer - the answer $y$ or a string "TAT" - Bo can't solve this problem.

Sample Input

233

233333333333333333333333333333333333333333333333333333333

Sample Output

TAT

Source

2016 Multi-University Training Contest 3

Recommend

wange2014

题意：给你一个数问你需要不断开根多少次结果等于1 超过5次输出 TAT

题解：由于有

很容易发现是 $2^{32}，所以我们先比较输入的数字是否比这个大，然后再暴力开根$

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 //#include<bits/stdc++.h>
 8 #include<iostream>
 9 #include<cstring>
10 #include<cmath>
11 #include<cstdio>
12 #define ll long long
13 #define mod 1000000007
14 #define PI acos(-1.0)
15 using namespace std;
16 char a[205];
17 ll ans;
18 int main()
19 {
20       while(scanf("%s",a)!=EOF){
21         ans=0;
22         int len=strlen(a);
23         if(len>10||(len==1&&a[0]=='0'))
24          printf("TAT
");
25         else
26         {
27             for(int i=0;i<len;i++)
28                 ans=ans*10+a[i]-'0';
29             int jishu=0;
30             while(1)
31             {
32                 jishu++;
33                 double exm=ans;
34                 exm=sqrt(exm);
35                 ans=(ll)exm;
36                 if(ans==1)
37                     break;
38             }
39             if(jishu<=5)
40              printf("%d
",jishu);
41             else
42              printf("TAT
");
43         }
44     }
45     return 0;
46 }