高精度乘法-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]);
}
}
}
}