首页 > 代码库 > zoj2562：搜索+数论(反素数)

zoj2562：搜索+数论(反素数)

2024-07-21 19:51:50   218人阅读

题目大意：求n以内因子数量最多的数  n的范围为1e16

其实相当于求n以内最大的反素数。。。

由素数中的 算数基本原理

设d(a)为a的正因子的个数，则

              d(n)=(a1+1)(a2+1).....*(an+1);

又由反素数的性质2：

              p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....

我们可以指定搜索策略和剪枝

详见代码和注释

#include <iostream>#include<stdio.h>#include<algorithm>#include<math.h>using namespace std;long long n;long long a[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};//这些素数全部乘积已经超过了1e16，所以不用再往下面乘了long long ans,ans0;void dfs(long long num,long long sum,long long limit,long long po)//limit 存储上一个素数的指数 相当于反素数性质中的t(i-1)，由性质可知ti<=t(i-1){    if(num>n)        return;    if(sum==ans0)    {        ans=min(ans,num);    }    if(sum>ans0)    {        ans0=sum;        ans=num;    }    long long p=1;    for(int i=1;i<=limit;i++)    {        p*=a[po];        if(p*num>n)            break;        dfs(num*p,sum*(i+1),i,po+1);    }    return;}int main(){    while(scanf("%lld",&n)!=EOF)    {        ans0=0;        ans=0;        if(n==1)        {            puts("1");            continue;        }        dfs(1,1,100,0);        cout<<ans<<endl;    }    return 0;}

 

zoj2562：搜索+数论(反素数)


联系
我们