求最小的有2^(500500)个因子的数

我们知道，120有16个因子(不信自己数一数)。事实上120也是最小的有16个因子的数。

请你找出最小的有2的500500次方个因子的数。

因为数据过大，可以结果对500500507取模。

思路：

以120为例，120的质因数分解为2*2*2*3*5。那么和16有什么关系呢？很明显，从这5个数中随机选[0-5]个数共有多少种方法呢。刚好16种。及4*2*2种。2有4种选法，3有2种（选或不选），5也2种。所以组合方式为16种。

现在看这道题，2^500500个因子，与2相关，1个素数p有2^1种，3个p有2^2种，7个有1^3种……

现在我们有500500个位置，那么1个p占1位，若p有多个，则剩下的2个占1位，然后剩下的4个1位，8个1位……而2^32已经超int范围了，所以次方最大为16。然后我们打表求出前500500个素数，对着500500个素数中分别插入2^2,2^4,2^8,2^16,3^2,3^4,3^8,5^2……插入的前提是p^n要小于500500个数中的最大数。最后求出这500500个数之后，只需相乘就是该数了。有了思路就可以写代码了。

答案取模500500507后为35407281

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 500500507;
const ll mi = 500500+1;
const ll maxn = 2e7;
ll a[4] = {2, 4, 8, 16};
ll prime[mi+100];
ll check[maxn], tot;
void init(){
    memset(check, 0, sizeof(check));
    prime[tot++] = 1;
    for (ll i = 2; i < maxn; ++i){
        if(!check[i]){
            prime[tot++] = i;
        }
        if(tot == mi){
            break;
        }
        for (ll j = 1; j < tot; ++j){
            if (i * prime[j] > maxn){
                break;
            }
            check[i*prime[j]] = 1;
            if (i % prime[j] == 0){
                break;
            }
        }
    }
}
ll Pow(ll a, ll b){
    ll ans = 1;
    for(ll i = 1; i <= b; i++){
        ans *= a;
        if(ans > prime[tot-1]){
            ans = prime[tot-1]+1;
            break;
        }
    }
    return ans;
}
int main(){
    init();
    priority_queue<ll>que;
    que.push(1);
    ll Size = 1;
    ll Top = 4;
    for(ll i = 1; i < mi; i++){
        if(Size >= mi){
            if(prime[i] >= que.top()){
                break;
            }
            else{
                que.pop();
                que.push(prime[i]);
                for(ll j = 0; j < Top; j++){
                    if(Pow(prime[i], a[j]) >= prime[tot-1]){
                        Top = j;
                        break;
                    }
                    if(Pow(prime[i], a[j]) >= que.top()){
                        Top = j;
                        break;
                    }
                    else{
                        que.pop();
                        que.push(Pow(prime[i], a[j]));
                    }
                }
            }
        }
        else{
            que.push(prime[i]);
            Size++;
            for(ll j = 0; j < Top; j++){
                if(Pow(prime[i], a[j]) >= prime[tot-1]){
                    Top = j;
                    break;
                }
                if(Size >= mi){
                    if(Pow(prime[i], a[j]) >= que.top()){
                        Top = j;
                        break;
                    }
                    else{
                        que.pop();
                        que.push(Pow(prime[i], a[j]));
                    }
                }
                else{
                    if(Pow(prime[i], a[j]) >= prime[tot-1]){
                        Top = j;
                        break;
                    }
                    que.push(Pow(prime[i], a[j]));
                    Size++;
                }
            }
        }
    }
    ll ans = 1;
    int SI = 0;
    while(!que.empty()){
        ans *= que.top();
        que.pop();
        ans%=mod;
        SI++;
    }
    cout<<ans<<endl;
    return 0;
}