大致题意: 给定一个高精大整数\(n\),求\(\lfloor\sqrt[m]n\rfloor\)。
前言
其实这种题并没有什么写的价值,纯粹是想检测一下自己的码力,仅此而已。
然而,\(WA\)了,还是错在几个不容易察觉的细节,例如输出时忘记特判\(0\)。单个数据还只是错一两个点,可如果是多组数据的话(现在一般都喜欢这样出题),可能因此就直接爆零凉凉。
遥想当年,还是小学的时候,根本不会任何数据结构(甚至于最基本的线段树)或者算法的我,正是凭着暴搜和模拟两个方法招摇撞骗(分),在\(NOIP2016\)普及组中还取得了不错的成绩。
现在想来,或许让小学的我,来做这道题,甚至可能直接\(A\)掉,吊打如今的我。
三年前,过去的我,什么都不会,做题时所能倚靠的,只是模拟以及种种暴力。
三年后,现在的我,似乎依旧什么都不会,若说与过去有什么不同,大概就是模拟、暴力都也总是写挂,连这最根本的倚靠,都已经失去了。
更可悲的是,我的心中好像的确有什么东西已经彻底的消逝了。
这么说来,如今的我,大概已经彻底成了个废物吧。
二分+高精
这道题的做法很显然,利用高精度,二分答案+快速幂验证,没什么可说。
不过为了防止\(TLE\)可能需要压下位。
具体实现详见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 10000
#define ull unsigned long long
using namespace std;
int m;
struct BigInt//高精度
{
#define base 1000000
int len;ull a[N+5];I BigInt() {len=0,memset(a,0,sizeof(a));}
I ull& operator [] (CI x) {return a[x];}
I void read()//读入
{
string s;cin>>s;RI i,l=s.length();len=(l+5)/6;
for(i=0;i^l;++i) (a[(l-i+5)/6]*=10)+=s[i]&15;
}
I void write()//输出
{
if(!len) return (void)(puts("0"));//特判0
for(RI i=len;i;--i) i^len&&//注意除最高位外输出每一位的前导0
(
a[i]<1e5&&putchar(48),a[i]<1e4&&putchar(48),a[i]<1e3&&putchar(48),
a[i]<100&&putchar(48),a[i]<10&&putchar(48)
),printf("%d",a[i]);
}
I friend BigInt operator * (Con BigInt& A,Con BigInt& B)//乘法
{
BigInt t;RI i,j;for(i=1;i<=A.len;++i) for(j=1;j<=B.len;++j) t[i+j-1]+=A.a[i]*B.a[j];
for(t.len=A.len+B.len-1,i=1;i<=t.len;++i) t[i+1]+=t[i]/base,t[i]%=base;
W(t[t.len+1]) ++t.len,t[t.len+1]+=t[t.len]/base,t[t.len]%=base;return t;
}
I friend BigInt operator ^ (BigInt x,RI y)//快速幂
{
BigInt t;t.len=t[1]=1;W(y) y&1&&(t=t*x,0),x=x*x,y>>=1;
return t;
}
I friend bool operator < (Con BigInt& A,Con BigInt& B)//比大小
{
if(A.len^B.len) return A.len<B.len;//先比长度
for(RI i=A.len;i;--i) if(A.a[i]^B.a[i]) return A.a[i]<B.a[i];return 0;//从高到低逐位比较
}
}n,ans;
int main()
{
RI i,l,r,mid,f=0;for(scanf("%d",&m),n.read(),ans.len=i=n.len/m+1;i;--i)//从高到低枚举每一位依次二分
{
l=0,r=1e6;W(l<r) ans[i]=mid=l+r+1>>1,n<(ans^m)?(r=mid-1):(l=mid);//二分答案+验证
if(!f&&!l) {--ans.len;continue;}f=1,ans[i]=l;
}return ans.write(),0;
}