zoj 1562 反素数 附上个人对反素数性质的证明

时间：2024-11-05 21:03:26

反素数的定义：对于不论什么正整数zoj 1562 反素数 附上个人对反素数性质的证明，其约数个数记为zoj 1562 反素数 附上个人对反素数性质的证明。比如zoj 1562 反素数 附上个人对反素数性质的证明，假设某个正整数zoj 1562 反素数 附上个人对反素数性质的证明满足：对随意的正整

数zoj 1562 反素数 附上个人对反素数性质的证明。都有zoj 1562 反素数 附上个人对反素数性质的证明，那么称zoj 1562 反素数 附上个人对反素数性质的证明为反素数。

从反素数的定义中能够看出两个性质：

（1）一个反素数的全部质因子必定是从2開始的连续若干个质数。由于反素数是保证约数个数为zoj 1562 反素数 附上个人对反素数性质的证明的这个数zoj 1562 反素数 附上个人对反素数性质的证明尽量小

（2）相同的道理，假设zoj 1562 反素数 附上个人对反素数性质的证明，那么必有zoj 1562 反素数 附上个人对反素数性质的证明

个人理解性证明：

对（1）如果不是从2開始，那么如果n的最小素因素是k，把k换成2，2的次数仍等于k的次数，得到N，可知,N<n，而且f(n)==f(N)。与n是反素数矛盾

对(2)如果ti<tj   ti,tj各自是是质因数i,j的次数，i<j。那么将i的次数换成tj,j的次数换成ti 能够得到N 。满足N<n且f(n)==f(N)，与n是反素数矛盾

综上，两条性质得证

可能会疑惑，反素数的性质有个毛用！？

答案是：剪枝

先来一份TLE代码(2000ms+)

const int SIZE = 16;

const int MAXN = 65;

int p[SIZE] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

ll n,ans,ansnum;

void dfs(int dep, ll tmp , ll mx)

{

    if(tmp<=n)

    {

        if(mx>ansnum)

        {

            ans=tmp;

            ansnum=mx;

        }

        if(mx==ansnum)ans=min(tmp,ans);///

    }

    if(tmp>=n || dep>SIZE-1)return;

    ll tt=1;

    for(int i=0;i<SIZE;i++)

    {

        if(n/tt<tmp)break;

        dfs(dep+1,tmp*tt,mx*(i+1));

        tt*=p[dep];

    }

}

int main()

{

    //IN("zoj1562.txt");

    while(~scanf("%lld",&n))

    {

        ans=ansnum=0;

        dfs(0,1,1);

        printf("%lld\n",ans);

    }

    return 0;

}

TLE的原因是dfs太多，剪枝方法非常easy。

1、DFS的时候，是从小的素数開始，由性质1，必须是次数从1開始而不是0開始。这样就剪下了一块

2、DFS的时候，深度为dep的那一层，循环处理的是prm[dep]的i次方，那么由性质2。其上限不能超过上一层的次数，又零零碎碎剪下了不少

另外注意两点：

1、由于害怕超过long long 所以用除法

if(n/tt<tmp)break;

2、注意求反素数这行代码：（是为了满足定义）

<pre code_snippet_id="457113" snippet_file_name="blog_20140824_2_8087056" name="code" class="cpp">if(mx==ansnum)ans=min(tmp,ans);


#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <iomanip>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdout)

const ll ll_INF = ((ull)(-1))>>1;

const double EPS = 1e-8;

const int INF = 100000000;

const int SIZE = 16;

const int MAXN = 65;

int p[SIZE] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

ll n,ans,ansnum;

void dfs(int dep, ll tmp , ll mx,int num)

{

    if(tmp<=n)

    {

        if(mx>ansnum)

        {

            ans=tmp;

            ansnum=mx;

        }

        if(mx==ansnum)ans=min(tmp,ans);///

    }

    if(tmp>=n || dep>SIZE-1)return;

    ll tt=1;

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

    {

        tt*=p[dep];

        if(n/tt<tmp)break;

        dfs(dep+1,tmp*tt,mx*(i+1),i+1);

    }

}

int main()

{

    //IN("zoj1562.txt");

    while(~scanf("%lld",&n))

    {

        ans=ansnum=0;

        dfs(0,1,1,MAXN);

        printf("%lld\n",ans);

    }

    return 0;

}




相关文章