高精度乘法-17南宁区域赛F -The Chosen One

题目大意：给你一个n，然后从1~n隔一个选一个，挑出一个集合然后从集合中继续隔一个挑一个，直到只有一个数，问最后一个数是多少？2<=n<=10⁵⁰

例如n=5,先选出2，4最后选择4。n=12,先选出2，4，6，8，10，12，再选出4，8，12在选出8。

可以发现这个数字一定是偶数，并且是比n小中被2除最多次的一个数，所以发现就是找一个2的幂次的小于n的最大的数。代码如下：

 

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
string a[100005];
int t[1000005];
bool judge(string n,string a)
{
    if(n.size()<a.size())
        return true;
    else if(n.size()==a.size())
    {
        for(int i=0; i<a.size(); i++)
        {
            if(n[i]<a[i])
                return true;
            if(n[i]>a[i])
                return false;
        }
    }
    return false;
}

string fun(string a)
{

    memset(t,0,sizeof(t));
    for(int i=1; i<=a.size(); i++)
        t[i]=(a[a.size()-i]-'0')*2;
    for(int i=1; i<=a.size(); i++)
        if(t[i]>=10)
        {
            t[i+1]+=t[i]/10;
            t[i]=t[i]%10;
        }
    int len=a.size()+1;
    string a1;
    while(t[len]==0)
    {
        len--;
    }
    for(int i=len; i>=1; i--)
    {
        a1+=('0'+t[i]);
    }
    return a1;
}

int main()
{
    int t;
    cin>>t;
    string n;
    a[1]+='2';
    while(t--)
    {
        cin>>n;
        for(int i=1;; i++)
        {
            if(judge(n,a[i]))
            {
                cout<<a[i-1]<<endl;
                break;
            }
            else
            {
                if(a[i+1].size()==0)
                    a[i+1]=fun(a[i]);
            }
        }
    }
}