Sqrt Bo

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

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

TAT

Author

绍兴一中

Source

2016 Multi-University Training Contest 3

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5752

题意：给你一个数，对这个数进行连续开方，这个数能在5次以内开方(每次开方都是向下取整)，使得最后结果等于1，输出开方次数，否则输出TAT

分析：看起来这道题怪吓人的，10^100次，lfh跟我说这道题很难，要用字符串啥玩意来着，然后算什么2^32的数还是啥的，弱弱菜鸡就随手扔了一个代码

枚举一波连续开5次根的数，然后。。。。竟然AC了，旁边的lfh懵逼了：这也行？(弱弱的说他好像Wa了好几发的样子)，此题数据是10^100，建议开long double型

其次是。。。。。我特别嫌弃这种要连续输入的题，每次害得我找错误找半天QAQ！

下面给出AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long double ll;

 inline ll gcd(ll x)

 {

     int k,t;

     int flag=;

     for(k=;k<=;k++)

     {

         x=(long long)sqrt(x);

         if(x==)

         {

             flag=;

             t=k;

             break;

         }

     }

     if(flag)

         return t;

     return ;

 }

 int main()

 {

     ll n;

     while(cin>>n)

     {

     if(!gcd(n))

         cout<<"TAT"<<endl;

     else cout<<gcd(n)<<endl;

     }

     return ;

 }

巴特西

HDU 5752 Sqrt Bo【枚举，大水题】

Sqrt Bo

最新文章

热门文章