反素數求解+反素數打表

問題描述:

對于任何正整數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]中約數在大的反素數-->求約數最多的數

如果求約數的個數 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 <cstring>
#define ll long long
using namespace std;

const int inf = 999999999;
const int prime[16]= {1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int n;
ll bnum,bsum;
//目前枚舉到的數；枚舉到的第K大的質因子；該數的約數個數；質因子個數上限。
void getantiprime(ll num,ll k,ll sum,ll limit)
{
    //如果約數個數更多，将最優解更新為目前數。
    if (bsum < sum)
    {
        bsum = sum;
        bnum = num;
    }
    //如果約數個數相同，将最優解更新為較小的數。
    if (bsum == sum && bnum > num) bnum = num;
    if (k > 10) return ;
    ll tmp = num;
     //開始枚舉每個質因子的個數。
    for (int i = 1; i <= limit; ++i)
    {
        if (tmp*prime[k] > n) break;
        tmp = tmp*prime[k];
        getantiprime(tmp,k + 1,sum*(i + 1),i);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        bsum = -inf; bnum = inf;
        scanf("%d",&n);
        getantiprime(1,1,1,50);
        printf("%lld\n",bnum);
    }
    return 0;
}
      

#include<iostream>
#include<cstring>
#include <cstdio>
#define maxn 600000
using namespace std;
 
int dp[600001];
int main()
{
    int i,j;
    freopen("out.txt","w",stdout);
    memset(dp,0,sizeof(dp));
    for(i=1;i<=maxn;i++)
    {
        for(j=1;i*j<=maxn;j++)
        {
                dp[i*j]++;
        }
    }
    int max=0;
    for(i=2;i<=maxn;i++)
    {
        if(dp[i]>max)
        {
            max=dp[i];
            cout<<i<<",";
        }
    }
    cout<<endl<<endl;
    max=0;
    for(i=2;i<=maxn;i++)
    {
        if(dp[i]>max)
        {
            max=dp[i];
            cout<<dp[i]<<",";
        }
    }
    return 0;
}