HDU-2016 Multi-University Training Contest 3-Sqrt Bo-大数开方

待我称王封你为后i 2022-09-24 05:24 164阅读 0赞

# Sqrt Bo #

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

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

## 题目意思： ##

对一个数开方，能在五次之内取整得到0的就输出次数；不能或者是0的话就输出TAT。。

## 解题思路： ##

这题longlong暴力就能过，队友很快就过了~然而我当时没想到，只想到了大数……QwQ

吭哧吭哧改了半天……才过…╮(╯▽╰)╭

longlong的代码很简单我就不写了，下面给出我写的大数的…这个模板说不定以后用的上呢~2333

#include <iostream>
    using namespace std;
    #include <stdlib.h>
    #include <string.h>
    #define MAXN 1000000
    int j,l,size,num,x[MAXN];
    char ch[MAXN],ans[MAXN];
    void sqrt(char *str)//大数求平方
    {
        double i,r,n;
        size=strlen(str);
        if (size%2==1)
        {
            n=str[0]-48;
            l=-1;
        }
        else
        {
            n=(str[0]-48)*10+str[1]-48;
            l=0;
        }
        r=0,num=0;
        while (true)
        {
            i=0;
            while (i*(i+20*r)<=n)
                ++i;
            --i;
            n-=i*(i+20*r);
            r=r*10+i;
            x[num]=(int)i;
            ++num;
            l+=2;
            if (l>=size)
                break;
            n=n*100+(double)(str[l]-48)*10+(double)(str[l+1]-48);
        }
    
    
    }
    int main()
    {
        while (cin>>ch)
        {
            int flag=0;
            sqrt(ch);
            if((x[num-1]==1)&&num==1)//注意判断条件
            {
                cout<<"1"<<endl;
                flag=1;
                goto A;
            }
            for(int i=2; i<=5; ++i)//最多计算五次
            {
                for (j=0; j<num; ++j)
                    ans[j]='0'+x[j];//int转char
                ans[num]='\0';//注意末尾别忘了加结束符
                //cout<<ans<<endl;
                sqrt(ans);//开方
              if((x[num-1]==1)&&num==1)
                {
                    cout<<i<<endl;//输出次数
                    flag=1;//标记
                    break;
                }
            }
           A: if(!flag)
                cout<<"TAT"<<endl;//超过五次或者为0时
        }
        return 0;
    }