题解 P1128 [HNOI2001] 求正整数

说实话,是一个很好的题目。里面有很多新的思路。

传送门

首先, csy 大佬告诉我一个定理。

假设 \(N = \prod\limits p_i^{k_i}\) 那么 \(N\) 的因数个数为 \(\prod\limits {(k_i+1)}\)

显然,在这道题里 \(n = \prod\limits {(k_i+1)}\)

这就很好用了,那么我就想到了去将输入的 \(n\) 因数分解,就是找到那些个 \(k_i+1\) 。

在一节体育课上,我想到了其实每一种分解方法都是一种合法的答案。这时候不是只要找每一种分解就 ok 了吗? 思考一下时间复杂度,大概是在 \(\mathbf{O}(n\sqrt n)\) 左右。

看一眼讨论版: 高精度,掏出之前写过的高精板子。

直接写好提交。

#include <bits/stdc++.h>
#define debug puts("I ak IOI several times");
#define pb push_back
using namespace std;
template <typename T>inline void read(T& t){
    t=0; register char ch=getchar(); register int fflag=1;
    while(!('0'<=ch&&ch<='9')){if(ch=='-') fflag=-1;ch=getchar();}
    while(('0'<=ch&&ch<='9')){t=((t<<1)+(t<<3))+ch-'0'; ch=getchar();} t*=fflag;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){
    read(t);read(args...);
}
template <typename T>inline void write(T x){
    if(x<0) putchar('-'),x=~(x-1); int s[40],top=0;
    while(x) s[++top]=x%10,x/=10; if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}
struct GJ{
    static const int M=20087;
    int num[M+10],len;
    bool __fu;
    GJ(){clean();}
    void clean(){
        memset(num,0,sizeof(num));
        len=1;
        __fu=0;
    }
    void Read(){
        char str[M+10];
        scanf("%s",str);
        len=strlen(str);
        if(str[0]=='-'){
            __fu=1;
            for(register int i=1;i<len;++i)
               num[i]=str[len-i]-'0';
            len--;
        }else{
            for(register int i=1;i<=len;++i)
                num[i]=str[len-i]-'0';
        }
    }
    void Write(bool IakIOI){
        if(__fu) putchar('-');
        for(register int i=len;i>=1;--i)
            putchar(num[i]+'0');
        if(IakIOI) puts("");
        else /*您输出了空气。*/;
    }
    template <typename T>inline void itoBig(T x){
        clean();
        while(x!=0){
            num[len++]=x%10;
            x/=10;
        }
        if(len!=1)len--;
    }
    template <typename T>inline GJ turnGJ(T x){
        GJ ___gj;
        if(x<0){
            x=abs(x);
            ___gj.__fu=1;
        }
        while(x!=0){
            ___gj.num[___gj.len++]=x%10;
            x/=10;
        }
        if(___gj.len!=1)___gj.len--;
        return ___gj;
    }
    bool operator < (const GJ &cmp)const{
        if(len!=cmp.len) return len<cmp.len;
        for(int i=len;i>=1;--i)
            if(num[i]!=cmp.num[i]) return num[i]<cmp.num[i];
        return false;
    }
    bool operator > (const GJ &cmp)const{return cmp<*this;}
    bool operator <= (const GJ &cmp)const{return !(cmp<*this);}
    bool operator != (const GJ &cmp)const{return cmp<*this||*this<cmp;}
    bool operator == (const GJ &cmp)const{return !(cmp<*this||*this<cmp);}
    GJ operator + (const GJ &A)const{
        if(A.__fu&&__fu){
            auto _____tmp=*this,____tmp=A;
            _____tmp.__fu=0;____tmp.__fu=0;
            auto ___S=_____tmp+____tmp;
            ___S.__fu=1;
            return ___S;
        }
        if(A.__fu){
            auto ____tmp=A;
            ____tmp.__fu=0;
            auto ___S=*this-____tmp;
            return ___S;
        }
        if(__fu){
            auto ___tmp=*this;
            ___tmp.__fu=0;
            auto ___S=A-___tmp;
            return ___S;
        }
        GJ S;
        S.len=max(len, A.len);
        for(int i=1;i<=S.len;++i){
            S.num[i]+=num[i]+A.num[i];
            if(S.num[i]>=10){
                S.num[i]-=10;
                S.num[i+1]++;
            }
        }
        while(S.num[S.len+1])S.len++;
        return S;
    }
    GJ operator - (const GJ &A)const{
        if(A.__fu&&__fu){
            auto _S=A;
            _S.__fu=0;
            auto __S=*this+_S;
            return __S;
        }
        if(A.__fu){
            auto _S=A;
            _S.__fu=0;
            auto __S=*this+_S;
            return __S;
        }
        if(__fu){
            GJ _tmpp,_tmppp;
            _tmpp=*this;
            _tmpp.__fu=0;
            _tmppp=A;
            _tmppp.__fu=0;
            auto SSS=_tmpp+_tmppp;
            SSS.__fu=1;
            return SSS;
        }
        if(*this<A){
            putchar('-');
            auto S=A-*this;
            return S;
        }
        GJ S;
        S.len=max(len,A.len);
        for(int i=1;i<=S.len;++i){
            S.num[i]+=num[i]-A.num[i];
            if(S.num[i]<0){
                S.num[i]+=10;
                S.num[i+1]--;
            }
        }
        while(!S.num[S.len]&&S.len>1)S.len--;
        return S;
    }
    GJ operator * (const GJ &A)const{
        GJ S;
        if((A.__fu xor __fu)) S.__fu=1;
        if((A.len==1&&A.num[1]==0)||(len==1&&num[1]==0)) return S;
        S.len=A.len+len-1;
        for(int i=1;i<=len;++i)
            for(int j=1;j<=A.len;++j){
                S.num[i+j-1]+=num[i]*A.num[j];
                S.num[i+j]+=S.num[i+j-1]/10;
                S.num[i+j-1]%=10;
            }
        while(S.num[S.len+1])S.len++;
        return S;
    }
    GJ operator / (const GJ &A)const{
        GJ S;
        if((A.__fu xor __fu)) S.__fu=1;
        if((A.len==1&&A.num[1]==0)||(len==1&&num[1]==0))return S;
        GJ R,N;
        S.len=0;
        for(int i=len;i>=1;--i){
            N.itoBig(10);
            R=R*N;
            N.itoBig(num[i]);
            R=R+N;
            int flag=-1;
            for(register int j=1;j<=10;++j){
                N.itoBig(j);
                if(N*A>R){
                    flag=j-1;
                    break;
                }
            }
            S.num[++S.len]=flag;
            N.itoBig(flag);
            R=R-N*A;
        }
        for(register int i=1;i<=len/2;++i)swap(S.num[i],S.num[len-i+1]);
        while(!S.num[S.len]&&S.len>1)S.len--;
        return S;
    }
    GJ operator % (const GJ &A)const{
        GJ S;
        GJ P=*this/A;
        S=*this-P*A;
        return S;
    }
    void operator = (const GJ &A){
        for(register int i=1;i<=A.len;++i)
            num[i]=A.num[i];
        len=A.len;
        __fu=A.__fu;
    }
};
const int MAXN=50005;
int n; 
GJ ans;
int prime[MAXN],cnt;
bitset<MAXN>b;
void ss(int K){
	b[1]=b[0]=1;
	for(register int i=1;i*i<=K;++i)
		if(!b[i]) for(register int j=2;j*i<=K;++j) b[i*j]=1;
	for(register int i=1;i<=K;++i) if(!b[i]) prime[++cnt]=i;
	return;
}
GJ quick_power(GJ x,int k){
	if(k==1) return x;
	if(!k) return ans.turnGJ(1);
	GJ f=quick_power(x,k/2);
	if(k&1) return f*f*x;
	else return f*f;
}
void print(){
	for(int i=1;i<=100;++i) cout<<prime[i]<<' ';
	cout<<endl;
}
void dfs(int x,GJ tmp,int dep){
//	cout<<x<<' ';
//	tmp.Write(1);
	if(x==1){
		if(ans==ans.turnGJ(0)) ans=tmp;
		else if(tmp<ans) ans=tmp;
		return;
	}
	if(tmp>ans&&ans!=ans.turnGJ(0)) return;
	for(register int i=2;i<=x;++i)
		if(x%i==0) dfs(x/i,tmp*quick_power(ans.turnGJ(prime[dep]),i-1),dep+1);
}
int main(){
	ss(MAXN);
	cin>>n;
	dfs(n,ans.turnGJ(1),1);
	ans.Write(1);
    return 0;
}
//Welcome back,Chtholly.

看一眼讨论 :注意 90 分的不是正解,我就看了一下,跟我的思路不一样。那怎么办呢。这时候是真想不到怎么做了,只好 窃取数据

input:50000
output:2749929944932170000

原来是炸在最大值了,我又预处理了一下因数,常数暴力卡,还是只有 90 分, 直接特判50000

实在想不到怎么优化了,又看了一眼题解。

原来是用对数优化,刚好最近 whk 学了对数。

有几个性质:

\(\log(x y)=\log(x)+\log(y)\)
\(\log(x^y)=y\log(x)\)

那我就不需要在每次比较 ans 与 tmp 大小的时候都用高精比较了,而且也不用每一次都把答案算出来了。 只需要在结束的时候用快速幂弄弄就 ok 了。

因为 c++ 算 \(\log\) 比较慢,所以预处理在数组里。

我现在只需要开一个 struct 里面就存好在 \(N = \prod\limits p_i^{k_i}\) 里的每一个 \(p_i\) 和 \(k_i\) 就ok了,然后把这个东西作为参数传。

比较大小的时候用 \(\log\) 的特性比较,最后的 ans 用快速幂就解决了。

比较了一下,优化还是非常明显的 700ms -> 20ms

#include <bits/stdc++.h>
#define debug puts("I ak IOI several times");
#define pb push_back
using namespace std;
template <typename T>inline void read(T& t){
    t=0; register char ch=getchar(); register int fflag=1;
    while(!('0'<=ch&&ch<='9')){if(ch=='-') fflag=-1;ch=getchar();}
    while(('0'<=ch&&ch<='9')){t=((t<<1)+(t<<3))+ch-'0'; ch=getchar();} t*=fflag;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){
    read(t);read(args...);
}
template <typename T>inline void write(T x){
    if(x<0) putchar('-'),x=~(x-1); int s[40],top=0;
    while(x) s[++top]=x%10,x/=10; if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}
struct GJ{
    static const int M=20000;
    int num[M+10],len;
    bool __fu;
    GJ(){clean();}
    void clean(){
        memset(num,0,sizeof(num));
        len=1;
        __fu=0;
    }
    void Read(){
        char str[M+10];
        scanf("%s",str);
        len=strlen(str);
        if(str[0]=='-'){
            __fu=1;
            for(register int i=1;i<len;++i)
               num[i]=str[len-i]-'0';
            len--;
        }else{
            for(register int i=1;i<=len;++i)
                num[i]=str[len-i]-'0';
        }
    }
    void Write(bool IakIOI){
        if(__fu) putchar('-');
        for(register int i=len;i>=1;--i)
            putchar(num[i]+'0');
        if(IakIOI) puts("");
        else /*您输出了空气。*/;
    }
    template <typename T>inline void itoBig(T x){
        clean();
        while(x!=0){
            num[len++]=x%10;
            x/=10;
        }
        if(len!=1)len--;
    }
    template <typename T>inline GJ turnGJ(T x){
        GJ ___gj;
        if(x<0){
            x=abs(x);
            ___gj.__fu=1;
        }
        while(x!=0){
            ___gj.num[___gj.len++]=x%10;
            x/=10;
        }
        if(___gj.len!=1)___gj.len--;
        return ___gj;
    }
    bool operator < (const GJ &cmp)const{
        if(len!=cmp.len) return len<cmp.len;
        for(int i=len;i>=1;--i)
            if(num[i]!=cmp.num[i]) return num[i]<cmp.num[i];
        return false;
    }
    bool operator > (const GJ &cmp)const{return cmp<*this;}
    bool operator <= (const GJ &cmp)const{return !(cmp<*this);}
    bool operator != (const GJ &cmp)const{return cmp<*this||*this<cmp;}
    bool operator == (const GJ &cmp)const{return !(cmp<*this||*this<cmp);}
    GJ operator + (const GJ &A)const{
        if(A.__fu&&__fu){
            auto _____tmp=*this,____tmp=A;
            _____tmp.__fu=0;____tmp.__fu=0;
            auto ___S=_____tmp+____tmp;
            ___S.__fu=1;
            return ___S;
        }
        if(A.__fu){
            auto ____tmp=A;
            ____tmp.__fu=0;
            auto ___S=*this-____tmp;
            return ___S;
        }
        if(__fu){
            auto ___tmp=*this;
            ___tmp.__fu=0;
            auto ___S=A-___tmp;
            return ___S;
        }
        GJ S;
        S.len=max(len, A.len);
        for(int i=1;i<=S.len;++i){
            S.num[i]+=num[i]+A.num[i];
            if(S.num[i]>=10){
                S.num[i]-=10;
                S.num[i+1]++;
            }
        }
        while(S.num[S.len+1])S.len++;
        return S;
    }
    GJ operator - (const GJ &A)const{
        if(A.__fu&&__fu){
            auto _S=A;
            _S.__fu=0;
            auto __S=*this+_S;
            return __S;
        }
        if(A.__fu){
            auto _S=A;
            _S.__fu=0;
            auto __S=*this+_S;
            return __S;
        }
        if(__fu){
            GJ _tmpp,_tmppp;
            _tmpp=*this;
            _tmpp.__fu=0;
            _tmppp=A;
            _tmppp.__fu=0;
            auto SSS=_tmpp+_tmppp;
            SSS.__fu=1;
            return SSS;
        }
        if(*this<A){
            putchar('-');
            auto S=A-*this;
            return S;
        }
        GJ S;
        S.len=max(len,A.len);
        for(int i=1;i<=S.len;++i){
            S.num[i]+=num[i]-A.num[i];
            if(S.num[i]<0){
                S.num[i]+=10;
                S.num[i+1]--;
            }
        }
        while(!S.num[S.len]&&S.len>1)S.len--;
        return S;
    }
    GJ operator * (const GJ &A)const{
        GJ S;
        if((A.__fu xor __fu)) S.__fu=1;
        if((A.len==1&&A.num[1]==0)||(len==1&&num[1]==0)) return S;
        S.len=A.len+len-1;
        for(int i=1;i<=len;++i)
            for(int j=1;j<=A.len;++j){
                S.num[i+j-1]+=num[i]*A.num[j];
                S.num[i+j]+=S.num[i+j-1]/10;
                S.num[i+j-1]%=10;
            }
        while(S.num[S.len+1])S.len++;
        return S;
    }
    GJ operator / (const GJ &A)const{
        GJ S;
        if((A.__fu xor __fu)) S.__fu=1;
        if((A.len==1&&A.num[1]==0)||(len==1&&num[1]==0))return S;
        GJ R,N;
        S.len=0;
        for(int i=len;i>=1;--i){
            N.itoBig(10);
            R=R*N;
            N.itoBig(num[i]);
            R=R+N;
            int flag=-1;
            for(register int j=1;j<=10;++j){
                N.itoBig(j);
                if(N*A>R){
                    flag=j-1;
                    break;
                }
            }
            S.num[++S.len]=flag;
            N.itoBig(flag);
            R=R-N*A;
        }
        for(register int i=1;i<=len/2;++i)swap(S.num[i],S.num[len-i+1]);
        while(!S.num[S.len]&&S.len>1)S.len--;
        return S;
    }
    GJ qpow (const GJ &A,int buff) const{
		if(buff==1) return A;
		GJ f=qpow(A,buff/2);
		if(buff&1) return f*f*A;
		else return f*f;
	}
    GJ operator % (const GJ &A)const{
        GJ S;
        GJ P=*this/A;
        S=*this-P*A;
        return S;
    }
    void operator = (const GJ &A){
        for(register int i=1;i<=A.len;++i)
            num[i]=A.num[i];
        len=A.len;
        __fu=A.__fu;
    }
};
const int MAXN=600;
int n;
int prime[MAXN],cnt;
bitset<MAXN>b;
double lg[800];
const int MAXM=50000;
vector<int>s[MAXM+5];
const int siz=32;
struct Info{
	int buf[siz+5];
	bool operator < (const Info & info)const{
		double a,b;a=b=0;
		for(int i=1;i<=siz;++i) a+=buf[i]*lg[prime[i]],b+=info.buf[i]*lg[prime[i]];
	//	cout<<a<<' '<<b<<endl;
		return a<b;
	}
	void add(int x,int S){
		buf[x]+=S; return;
	}
	void print(){
		for(int i=1;i<=siz;++i) cout<<buf[i]<<' ';
		cout<<endl;
	}
}fst;
void ss(int K){
	b[1]=b[0]=1;
	for(register int i=1;i*i<=K;++i)
		if(!b[i]) for(register int j=2;j*i<=K;++j) b[i*j]=1;
	for(register int i=1;i<=K;++i) if(!b[i]) prime[++cnt]=i;
	for(int i=1;i<=cnt;++i) lg[prime[i]]=log(prime[i]);
	return;
}
Info ans;
GJ ANS;
inline void dfs(int x,Info tmp,int dep){
/*	cout<<x<<' '<<dep<<' '<<":::::";
	tmp.print();*/
	if(ans<tmp) return;
	if(x==1){
		if(tmp<ans) ans=tmp;
		return;
	}
	for(int i=0;i<s[x].size();++i){
		tmp.add(dep,s[x][i]-1);
		dfs(x/s[x][i],tmp,dep+1);
		tmp.add(dep,-(s[x][i]-1));
	}
}
int main(){
	for(int i=1;i<=siz;++i) ans.buf[i]=10000,fst.buf[i]=0;
	for(int i=1;i<=MAXM;++i){
		for(int j=2;j*j<=i;++j){
			if(i%j==0){
				if(j*j==i) s[i].push_back(j);
				else{
					s[i].push_back(j);
					s[i].push_back(i/j);
				}
			}
		}
		s[i].push_back(i);
	}
	ss(MAXN);
	cin>>n;
	dfs(n,fst,1);
	ANS=ANS.turnGJ(1);
	for(int i=1;i<=siz;++i){
		if(!ans.buf[i]) break;
		ANS=ANS*ANS.qpow(ANS.turnGJ(prime[i]),ans.buf[i]);
	}
	ANS.Write(1);
    return 0;
}
//Welcome back,Chtholly.
上一篇:11.18训练赛


下一篇:Java多态