[HNOI2004]高精度开根

题目：洛谷P2293、BZOJ1213。

题目大意：给你$n,k(n\leq 10^{10000},k\leq 50)$，求$\lfloor \sqrt[k]{n}\rfloor$。

解题思路：高精度+二分+快速幂。

我压了九位。

这题真的卡的我丧心病狂啊！！开始无脑高精度，后来T的不知道哪去了。

首先高精度乘法中除法取模运算特别慢，要放在乘完后再处理。

还有最重要的优化：如果当前的答案的位数乘k减k+1大于n的位数，则不需要进行乘法，因为答案一定失败。

然后尽量减少传值，努力卡常即可。

可怜我压九位居然只输出八位，找了一小时错！

C++ Code：

%:pragma GCC optimize(2)

#include<cstring>

#include<cstdio>

using namespace std;

char READ[10200];

int k;

typedef unsigned long long ll;

struct BigInteger{

	typedef unsigned long long ll;

	static const ll base=1000000000;

	ll v[1992];

	int size;

	BigInteger():size(0){

		memset(v,0,sizeof v);

	}

	void print(){

		printf("%llu",v[size]);

		for(int i=size-1;i>0;--i)

		printf("%09llu",v[i]);

		putchar('\n');

	}

	void ch(const BigInteger& b){

		BigInteger c;

		for(int i=1;i<=size;++i)

		for(int j=1;j<=b.size;++j)

		c.v[i+j-1]+=(v[i]*b.v[j]);

		c.size=size+b.size+2;

		for(int i=1;i<=c.size;++i)

		c.v[i+1]+=c.v[i]/base,c.v[i]%=base;

		while(!c.v[c.size])--c.size;

		*this=c;

	}

	BigInteger operator +(const BigInteger& b)const{

		BigInteger c;

		c.size=size;

		if(size<b.size)c.size=b.size;

		for(int i=1;i<=c.size;++i){

			c.v[i]+=v[i]+b.v[i];

			c.v[i+1]=c.v[i]/base;

			c.v[i]%=base;

		}

		if(c.v[c.size+1])++c.size;

		return c;

	}

	BigInteger inc(){

		BigInteger c=*this;

		c.v[1]++;

		int now=1;

		while(c.v[now]>=base){

			c.v[now+1]++;

			c.v[now++]-=base;

		}

		if(c.v[c.size+1])++c.size;

		return c;

	}

	BigInteger dec(){

		BigInteger c=*this;

		c.v[1]--;

		int now=1;

		while(c.v[now]<0){

			c.v[now+1]--;

			c.v[now++]+=base;

		}

		if(!c.v[c.size])--c.size;

		return c;

	}

	bool operator <=(const BigInteger& b)const{

		if(size!=b.size)return size<b.size;

		for(int i=size;i>0;--i)

		if(v[i]!=b.v[i])return v[i]<b.v[i];

		return true;

	}

}a,l,r,mid,ans;

void read(){

	scanf("%s",READ);

	int len=strlen(READ);

	a.size=0;

	ll now=0,wid=1;

	for(int i=len-1;i+1;--i){

		now+=(READ[i]^'0')*wid;

		wid*=10;

		if(wid==1000000000){

			wid=1;

			a.v[++a.size]=now;

			now=0;

		}

	}

	if(now)a.v[++a.size]=now;

}

void average(){

	for(int i=mid.size;i;--i){

		mid.v[i-1]+=(mid.v[i]&1ll)*mid.base;

		mid.v[i]>>=1;

	}

	mid.v[0]=0;

	while(!mid.v[mid.size])--mid.size;

}

bool power(BigInteger a,int k){

	BigInteger p;

	p.size=p.v[1]=1;

	while(k){

		if(k&1)p.ch(a);

		if(p.size>::a.size)return false;

		a.ch(a);

		k>>=1;

	}

	return p<=::a;

}

int main(){

	scanf("%d",&k);

	read();

	if(k==1||a.size==0){

		a.print();

		return 0;

	}

	l.size=l.v[1]=1;

	r=a;

	while(l<=r){

		mid=l+r;

		average();

		if(mid.size*k-k+1<=a.size&&power(mid,k))

		l=(ans=mid).inc();else

		r=mid.dec();

	}

	ans.print();

	return 0;

}