1 条题解

  • 0
    @ 2019-09-27 20:32:55

    #include<bits/stdc++.h>
    using namespace std;
    long long n,ans=0,maxn=0;//maxn=每个小于n的数总约数和
    long long a[15]={0,2,3,5,7,11,13,17,19,23,29};
    //约数个数求法:设m=2^a+3^b+……+p^?(p是最大的质数) 则约数个数为(a+1)*(b+1)*……*(p+?)
    void solve(long long seat,long long value,long long limits,long long amount)
    {
    //seat=质因数位置 value=当前累计值 limits=每个质因数范围 amount=当前累计因数个数
    if(maxn<amount||(maxn==amount&&ans>value))
    {// 当每发现一个约数和比当前在计算的数的约数和还大的数时 || (两个数的总约数和相等&&但其中一个数大于另外一个数)
    ans=value;//找出最大的Antiprime数
    //这里注意是要选择一个相比更小的数 因为题目要求不大于n 所以每找出几个总约数和相等的数 就选最小的那个数
    //以免这个数大于n
    maxn=amount;//赋值maxn等于目前所能找到的最多的约数和的数的约数总和
    }
    if(seat==11) return ;//数据最大为2*10^9 所以质因子数最多10个
    for(long long i=1;i<=limits;i++)
    {
    value*=a[seat];
    if(value>n) return ;
    solve(seat+1,value,i,amount*(i+1));
    //solve(下一个质因数,当前累计值,一直递归到当前这个质因数最大使用范围,统计当前质因数使用个数)
    }
    }
    int main()
    {
    cin>>n;
    solve(1,1,31,1);//数据最大为2*10^9 2^31次 递归层数最大也就31
    cout<<ans<<endl;
    return 0;
    }
    //来自某届石光中学信竞苟蒻学长 愿看到此文的你 努力码题 为校争光

  • 1

信息

难度
9
分类
数学数论 点击显示
标签
递交数
2
已通过
2
通过率
100%
上传者