求最小的有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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#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;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!