题解 P2293 【[HNOI2004]高精度开根】

xukuan · 2019-10-22 08:08:05 · 题解

二分答案+高精度+卡常

一开始裸的高精，时间复杂度O(m\log_{10}^2n\log_2n)只有40分

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=20010;
ll m;
struct bignum{
    ll len,num[N];
    bignum(){len=0; memset(num,0,sizeof(num));}
}n,one,zero,ans;

inline bignum read(){
    bignum ans;
    string s; cin>>s;
    for(ll i=0; i<s.size(); i++) ans.num[s.size()-i]=s[i]-48;
    ans.len=s.size();
    return ans;
}

inline void write(bignum s){
    for(ll i=s.len; i>=1; i--) putchar(s.num[i]+48);
}

inline void operator ==(bignum &a,ll b){
    for(; b; b/=10) a.num[++a.len]=b%10;
}

inline bool operator <=(bignum a,bignum b){
    if(a.len>b.len) return 0;
    if(a.len<b.len) return 1;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]>b.num[i]) return 0;
        if(a.num[i]<b.num[i]) return 1;
    }
    return 1;
}

inline bool operator >(bignum a,bignum b){
    if(a.len>b.len) return 1;
    if(a.len<b.len) return 0;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]>b.num[i]) return 1;
        if(a.num[i]<b.num[i]) return 0;
    }
    return 0;
}

inline bignum operator +(bignum a,bignum b){
    bignum c;
    c.len=max(a.len,b.len);
    for(ll i=1; i<=c.len; i++){
        c.num[i]+=a.num[i]+b.num[i];
        c.num[i+1]+=c.num[i]/10;
        c.num[i]%=10;
    }
    if(c.num[c.len+1]) c.len++;
    return c;
}

inline bignum operator -(bignum a,bignum b){
    bignum c;
    c.len=a.len;
    for(ll i=1; i<=c.len; i++){
        c.num[i]=a.num[i]-b.num[i];
        if(c.num[i]<0){
            c.num[i]+=10;
            a.num[i+1]--;
        }
    }
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

inline bignum operator *(bignum a,bignum b){
    bignum c;
    for(ll i=1; i<=a.len; i++){
        for(ll j=1; j<=b.len; j++){
            c.num[i+j-1]+=a.num[i]*b.num[j];
            c.num[i+j]+=c.num[i+j-1]/10;
            c.num[i+j-1]%=10;
        }
    }
    c.len=a.len+b.len;
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

inline bignum operator /(bignum a,ll b){
    ll sum=0; bignum c;
    for(ll i=a.len; i>=1; i--){
        sum=sum*10+a.num[i];
        c.num[i]=sum/b;
        sum%=b;
    }
    c.len=a.len;
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

inline bool check(bignum a,ll b){
    bignum ans=one;
    for(ll i=1; i<=b; i++){
        ans=ans*a;
        if(ans>n) return 0;
    }
    return 1;
}

int main(){
    cin>>m; n=read();
    one==1; zero==0;
    bignum l=one,r=n;
    while(l<=r){
        bignum mid=(l+r)/2;
        if(check(mid,m)){
            ans=mid;
            l=mid+one;
        }
        else r=mid-one;
    }
    write(ans);
    return 0;
}

时间复杂度的大头是在高精度乘法上

最快的高精乘法是什么？FFT！

我加了FFT优化高精度乘法，时间复杂度优化到了O(m\log_{10}n \log_2 n \log_{2}\log_{10}n)，满心以为这次能过，结果。。。还是只有40分

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=20010;
const double pi=acos(-1);
ll m;
struct bignum{
    ll len,num[N];
    bignum(){len=0; memset(num,0,sizeof(num));}
}n,one,zero,ans,c;

inline void clear(bignum &a){
    memset(a.num,0,sizeof(a.num));
    a.len=0;
}

inline bignum read(){
    bignum ans;
    string s; cin>>s;
    for(ll i=0; i<s.size(); i++) ans.num[s.size()-i]=s[i]-48;
    ans.len=s.size();
    return ans;
}

inline void write(bignum s){
    for(ll i=s.len; i>=1; i--) cout<<s.num[i];
}

inline void operator ==(bignum &a,ll b){
    for(; b; b/=10) a.num[++a.len]=b%10;
}

inline bool operator <=(bignum a,bignum b){
    if(a.len>b.len) return 0;
    if(a.len<b.len) return 1;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]>b.num[i]) return 0;
        if(a.num[i]<b.num[i]) return 1;
    }
    return 1;
}

inline bool operator >(bignum a,bignum b){
    if(a.len>b.len) return 1;
    if(a.len<b.len) return 0;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]>b.num[i]) return 1;
        if(a.num[i]<b.num[i]) return 0;
    }
    return 0;
}

inline bignum operator +(bignum a,bignum b){
    clear(c);
    c.len=max(a.len,b.len);
    for(ll i=1; i<=c.len; i++){
        c.num[i]+=a.num[i]+b.num[i];
        c.num[i+1]+=c.num[i]/10;
        c.num[i]%=10;
    }
    if(c.num[c.len+1]) c.len++;
    return c;
}

inline bignum operator -(bignum a,bignum b){
    clear(c);
    c.len=a.len;
    for(ll i=1; i<=c.len; i++){
        c.num[i]=a.num[i]-b.num[i];
        if(c.num[i]<0){
            c.num[i]+=10;
            a.num[i+1]--;
        }
    }
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

void FFT(complex<double> *a,ll n,ll op){
    if(!n) return;
    complex<double> a0[n],a1[n];
    for(ll i=0; i<n; i++){
        a0[i]=a[i<<1];
        a1[i]=a[i<<1|1];
    }
    FFT(a0,n>>1,op); FFT(a1,n>>1,op);
    complex<double> W(cos(pi/n),sin(pi/n)*op),w(1,0);
    for(ll i=0; i<n; i++,w*=W){
        a[i]=a0[i]+w*a1[i];
        a[i+n]=a0[i]-w*a1[i];
    }
}

complex<double> x[N],y[N];
inline bignum operator *(bignum a,bignum b){
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    ll n=a.len-1,m=b.len-1;
    for(ll i=0; i<=n; i++) x[i]=a.num[i+1];
    for(ll i=0; i<=m; i++) y[i]=b.num[i+1];
    for(m+=n,n=1; n<=m; n<<=1);
    FFT(x,n>>1,1); FFT(y,n>>1,1);
    for(ll i=0; i<n; i++) x[i]*=y[i];
    FFT(x,n>>1,-1);
    bignum c;
    for(ll i=0; i<=m; i++) c.num[i+1]=(ll)(fabs(x[i].real()/n+0.5));
    c.len=m+1;
    while(c.len>1&&c.num[c.len]==0) c.len--;
    for(ll i=1; i<=c.len; i++){
        c.num[i+1]+=c.num[i]/10;
        c.num[i]%=10;
    }
    while(c.num[c.len+1]){
        c.len++;
        c.num[c.len+1]+=c.num[c.len]/10;
        c.num[c.len]%=10;
    }
    return c;
}

inline bignum operator /(bignum a,ll b){
    ll sum=0; clear(c);
    for(ll i=a.len; i>=1; i--){
        sum=sum*10+a.num[i];
        c.num[i]=sum/b;
        sum%=b;
    }
    c.len=a.len;
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

inline bool check(bignum a,ll b){
    bignum ans=one;
    for(ll i=1; i<=b; i++){
        ans=ans*a;
        if(ans>n) return 0;
    }
    return 1;
}

int main(){
    cin>>m; n=read();
    one==1; zero==0;
    bignum l=one,r=n;
    while(l<=r){
        bignum mid=(l+r)/2;
        if(check(mid,m)){
            ans=mid;
            l=mid+one;
        }
        else r=mid-one;
    }
    write(ans);
    return 0;
}

去看了题解，说要压位，我就压了8位，时间复杂度O(\frac{\log_2{m}\log_{10}^2n\log_2n}{64})，现在有50分了

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=20010,mod=100000000,length=log(mod)/log(10);
ll m;
struct bignum{
    ll len,num[N];
    bignum(){len=0; memset(num,0,sizeof(num));}
}n,one,zero,ans,QAQ;

inline bignum read(){
    bignum ans;
    string s; cin>>s;
    for(ll r=s.size()-1; r>=0; r-=length){
        ans.len++;
        ll l;
        if(r>=length-1) l=r-length+1;
        else l=0;
        for(ll i=l; i<=r; i++) ans.num[ans.len]=ans.num[ans.len]*10+s[i]-48;
    }
    return ans;
}

inline void write(bignum s){
    printf("%lld",s.num[s.len]);
    for(ll i=s.len-1; i>=1; i--){
        for(ll j=mod/10; j>s.num[i]; j/=10) putchar('0');
        if(s.num[i]) printf("%lld",s.num[i]);
    }
}

inline void operator ==(bignum &a,ll b){
    for(; b; b/=mod) a.num[++a.len]=b%mod;
}

inline bool operator <=(bignum a,bignum b){
    if(a.len>b.len) return 0;
    if(a.len<b.len) return 1;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]>b.num[i]) return 0;
        if(a.num[i]<b.num[i]) return 1;
    }
    return 1;
}

inline bool operator >(bignum a,bignum b){
    if(a.len>b.len) return 1;
    if(a.len<b.len) return 0;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]>b.num[i]) return 1;
        if(a.num[i]<b.num[i]) return 0;
    }
    return 0;
}

inline bignum operator +(bignum a,bignum b){
    bignum c;
    c.len=max(a.len,b.len);
    for(ll i=1; i<=c.len; i++){
        c.num[i]+=a.num[i]+b.num[i];
        c.num[i+1]+=c.num[i]/mod;
        c.num[i]%=mod;
    }
    if(c.num[c.len+1]) c.len++;
    return c;
}

inline bignum operator -(bignum a,bignum b){
    bignum c;
    c.len=a.len;
    for(ll i=1; i<=c.len; i++){
        c.num[i]=a.num[i]-b.num[i];
        if(c.num[i]<0){
            c.num[i]+=mod;
            a.num[i+1]--;
        }
    }
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

inline bignum operator *(bignum a,bignum b){
    bignum c;
    for(ll i=1; i<=a.len; i++){
        for(ll j=1; j<=b.len; j++){
            c.num[i+j-1]+=a.num[i]*b.num[j];
            c.num[i+j]+=c.num[i+j-1]/mod;
            c.num[i+j-1]%=mod;
        }
    }
    c.len=a.len+b.len;
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

inline bignum operator /(bignum a,ll b){
    ll sum=0; bignum c;
    for(ll i=a.len; i>=1; i--){
        sum=sum*mod+a.num[i];
        c.num[i]=sum/b;
        sum%=b;
    }
    c.len=a.len;
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

inline bignum pow(bignum x,ll y){
    if(y==0) return one;
    if(y==1) return x;
    bignum t=pow(x,y/2);
    t=t*t;
    if(y&1) t=t*x;
    if(t>n) return QAQ;
    else return t;
}

int main(){
    cin>>m; n=read();
    one==1; zero==0;
    QAQ=n+one;
    bignum l=one,r=n;
    while(l<=r){
        bignum mid=(l+r)/2;
        if(pow(mid,m)<=n){
            ans=mid;
            l=mid+one;
        }
        else r=mid-one;
    }
    write(ans);
    return 0;
}

如果mid^m最小长度大于n的长度就跳出

AC与50之间就差这一点。。。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=20010,mod=100000000,length=log(mod)/log(10);
ll m;
struct bignum{
    ll len,num[N];
    bignum(){len=0; memset(num,0,sizeof(num));}
}n,one,ans;

inline bignum read(){
    bignum ans;
    string s; cin>>s;
    for(ll r=s.size()-1; r>=0; r-=length){
        ans.len++;
        ll l;
        if(r>=length-1) l=r-length+1;
        else l=0;
        for(ll i=l; i<=r; i++) ans.num[ans.len]=ans.num[ans.len]*10+s[i]-48;
    }
    return ans;
}

inline void write(bignum s){
    printf("%lld",s.num[s.len]);
    for(ll i=s.len-1; i>=1; i--){
        for(ll j=mod/10; j>s.num[i]; j/=10) putchar('0');
        if(s.num[i]) printf("%lld",s.num[i]);
    }
}

inline void give(bignum &a,ll b){
    for(; b; b/=mod) a.num[++a.len]=b%mod;
}

inline bool smallequal(bignum a,bignum b){
    if(a.len>b.len) return 0;
    if(a.len<b.len) return 1;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]>b.num[i]) return 0;
        if(a.num[i]<b.num[i]) return 1;
    }
    return 1;
}

inline bool big(bignum a,bignum b){
    if(a.len>b.len) return 1;
    if(a.len<b.len) return 0;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]>b.num[i]) return 1;
        if(a.num[i]<b.num[i]) return 0;
    }
    return 0;
}

inline bignum add(bignum a,bignum b){
    bignum c;
    c.len=max(a.len,b.len);
    for(ll i=1; i<=c.len; i++){
        c.num[i]+=a.num[i]+b.num[i];
        c.num[i+1]+=c.num[i]/mod;
        c.num[i]%=mod;
    }
    if(c.num[c.len+1]) c.len++;
    return c;
}

inline bignum dec(bignum a){
    if(a.len==1){
        a.num[1]--;
        return a;
    }
    bignum c=a;
    c.num[1]--;
    for(ll i=1; c.num[i]<0;){
        c.num[i]=mod-1;
        i++;
        c.num[i]--;
    }
    if(c.num[c.len]==0) c.len--;
    return c;
}

inline bignum mul(bignum a,bignum b){
    bignum c;
    for(ll i=1; i<=a.len; i++){
        for(ll j=1; j<=b.len; j++) c.num[i+j-1]+=a.num[i]*b.num[j];
    }
    c.len=a.len+b.len;
    for(ll i=1; i<=c.len; i++){
        c.num[i+1]+=c.num[i]/mod;
        c.num[i]%=mod;
    }
    while(c.len>1&&c.num[c.len]==0) c.len--;
    return c;
}

inline bignum div(bignum a){
    bignum c;
    for(ll i=a.len; i>=1; i--){
        if(a.num[i]&1) a.num[i-1]+=mod;
        c.num[i]=a.num[i]>>1;
    }
    if(c.num[a.len]) c.len=a.len;
    else c.len=a.len-1;
    return c;
}

inline bignum pow(bignum x,ll y){
    if(y==1) return x;
    bignum t=pow(x,y>>1);
    t=mul(t,t);
    if(y&1) t=mul(t,x);
    return t;
}

int main(){
    cin>>m; n=read();
    give(one,1);
    bignum l=one,r=n;
    while(smallequal(l,r)){
        bignum mid=div(add(l,r));
        if(mid.len*m-m+1<=n.len&&smallequal(pow(mid,m),n)){
            ans=mid;
            l=add(mid,one);
        }
        else r=dec(mid);
    }
    write(ans);
    return 0;
}