首页 > 代码库 > HDU5752-Sqrt Bo

HDU5752-Sqrt Bo

2024-10-23 10:19:02   208人阅读

Sqrt Bo

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


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
 
题意就是一个数最多开5次根号，能否变成1，输出开根号的次数，如果不存在或者超过5次就输出TAT
2*2=4，4*4=16，16*16=256，256*256=65536；65536*65536=4294967296，所以4294967296为极值了，直接与这个数比较就可以，
当然也可以和4013729316这个数比较，这个数连开5次根号，为1.999577。。。
因为数比较大，所以用数组存大数。
先判断一下，如果数的位数大于10位，肯定TAT，再将数组里的数变成我们要求的大数，再判断是否<极值数，然后再开根号，记录次数就可以了。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
typedef long long ll;
char a[N];
int main(){
    int len,ans;
    ll num,cnt;
    while(~scanf("%s",&a)){
        len=strlen(a);
        if(len>10)
            printf("TAT\n");
        else{
            num=0;
            for(int i=0;i<len;i++){                       //将数组里的数变成要求的数
                num=num*10+a[i]-‘0‘;
            }
            if(num>=4013729316||num==0)
                printf("TAT\n");
            else{
                ans=0;
                while(num!=1){
                   num=(ll)sqrt(num*1.0);                 //因为向下取整，所以强制转换一下
                   ans++;
                }
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

==

HDU5752-Sqrt Bo


联系
我们