hdu 5752 Sqrt Bo 水题

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; }
上一篇:HDU 5752


下一篇:【模拟】HDU 5752 Sqrt Bo