首页 > 代码库 > COGS 693. [SDOI2005]Antiprime数 唯一分解定理逆用

COGS 693. [SDOI2005]Antiprime数 唯一分解定理逆用

693. Antiprime数

★★   输入文件:antip.in   输出文件:antip.out   简单对比
时间限制:1 s   内存限制:128 MB

如果一个自然数n(n>=1),满足所有小于n的自然数(>=1)的约数个数都小于n的约数个数,则n是一个Antiprime数。譬如:1, 2, 4, 6, 12, 24。

任务:

编一个程序:

1、 从ANT.IN中读入自然数n。

2、 计算不大于n的最大Antiprime数。

3、将结果输出到ANT.OUT中。

 

输入( antip.in)

输入文件antip.in只有一个整数,n(1 <= n <= 2 000 000 000)。

 

输出(antip.out):

输出文件antip.out也只包含一个整数,即不大于n的最大Antiprime数。

 

样例输入( antip.in):

1000

 

样例输出(antip.out)

840

 

问题描述:(转载自vb4896)

对于任何正整数x,起约数的个数记做g(x).例如g(1)=1,g(6)=4.

定义:如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.

现在给一个N,求出不超过N的最大的反素数.

比如:输入1000 输出 840

思维过程:

求[1..N]中最大的反素数-->求约数最多的数(约数同样多取数值小的)

简单证明:

如果X是答案,但X不是约数最多的数,假设约数最多的数是Y,那么Y>X,否则不符合反质数的定义。

那么很明显Y也是一个反质数,且Y比X大,那么答案应该是Y而不是X。

如果求约数的个数 756=2^2*3^3*7^1

(2+1)*(3+1)*(1+1)=24

基于上述结论,给出算法:按照质因数大小递增顺序搜索每一个质因子,枚举每一个质因子

为了剪枝:

性质一:一个反素数的质因子必然是从2开始连续的质数.

因为最多只需要10个素数构造:2,3,5,7,11,13,17,19,23,29

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

#include<cstdio>#include<iostream>using namespace std;typedef long long ll;int prime[12]={0,2,3,5,7,11,13,17,19,21,23};//2*3*5*7*11*13*17*19*21*23>n,所以只需考虑到23即可ll n,BestSum,BestNum;//当前走到num这个数,接着用第k个素数,num的约数个数为sum,//第k个素数的个数上限为limitvoid solve(ll num,ll sum,ll limit,ll k){    if(sum>BestSum){        BestSum=sum;        BestNum=num;    }    else if(sum==BestSum&&num<BestNum){//约数个数一样时,取小数        BestNum=num;    }    for(int i=1;i<=limit;i++){//素数k取i个        num*=prime[k];        if(num>n) return ;        solve(num,sum*(1+i),i,k+1);    }}int main(){    freopen("antip.in","r",stdin);    freopen("antip.out","w",stdout);    cin>>n;    solve(1,1,10,1);    cout<<BestNum;    return 0;}

 

COGS 693. [SDOI2005]Antiprime数 唯一分解定理逆用