[HDU5752]Sqrt Bo

Problem Description

Let’s define the function f(n)=⌊n√⌋.

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

note:f1(n)=f(n),fy(n)=f(fy−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<10100).

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

3
TAT

Source

2016 Multi-University Training Contest 3

分析

由于有5次的这个限制，所以尝试寻找分界点。
很容易发现是2³²，所以我们先比较输入的数字是否比这个大，然后再暴力开根。
复杂度是O(loglogn)。
注意特判n=0的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
char str[105];
char m[]="4294967296";
long long num;
int main(){
	int t;
	int len;
	int flag;
	while(cin>>str){
		len = strlen(str);
		if(len>10){
		  printf("TAT\n");
		  continue;
		}
		else if(len == 10){
			flag = 0;
			for(int i = 0;i<len;i++){
				if(str[i]>m[i]){
					flag = 1;
					break;
				}
				else if(str[i]<m[i])
				  break;
			}
		}
		if(flag)
		  printf("TAT\n");
		else{
			num = 0;
			for(int i = 0;i < len;i++){
				num*=10;
				num+=str[i]-'0';
			}
			int ans = 0;
			while(num>1){
				ans++;
				num = floor(sqrt(num*1.0));
			}
			if(ans>5)
			  printf("TAT\n");
			else
				printf("%d\n",ans);
		}
	}
}