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
3
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代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long double ll;
4 inline ll gcd(ll x)
5 {
6 int k,t;
7 int flag=0;
8 for(k=1;k<=5;k++)
9 {
10 x=(long long)sqrt(x);
11 if(x==1)
12 {
13 flag=1;
14 t=k;
15 break;
16 }
17 }
18 if(flag)
19 return t;
20 return 0;
21 }
22 int main()
23 {
24 ll n;
25 while(cin>>n)
26 {
27 if(!gcd(n))
28 cout<<"TAT"<<endl;
29 else cout<<gcd(n)<<endl;
30 }
31 return 0;
32 }