Sqrt Bo

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5752

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

Hint

题意

给你一个数，问你最少开多少次，可以变成1。

如果超过五次还没有变成1，就输出TAT

题解：

象征性猜一猜，五次的根号不会很大。

1->3->15->255->65535->4294967295

那就最大就是4294967295了，超过就直接输出TAT好了

代码

#include<bits/stdc++.h>

using namespace std;

string s;

void solve(){

    if(s.size()>18){

        printf("TAT\n");

        return;

    }

    long long n = 0;

    for(int i=0;i<s.size();i++){

        n = n*10+s[i]-'0';

    }

    if(n==1){

        cout<<"0"<<endl;

        return;

    }

    for(int i=1;i<=5;i++){

        n = sqrt(n);

        if(n==1){

            cout<<i<<endl;

            return;

        }

    }

    cout<<"TAT"<<endl;

}

int main(){

    while(cin>>s)solve();

    return 0;

}