题目88：考察不同大小集合的最小积和数
Product-sum numbersA natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, is called a product-sum number:
For example, 6 = 1 + 2 + 3 = 1 × 2 × 3.
For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.
Hence for 2≤k≤6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.
In fact, as the complete set of minimal product-sum numbers for 2≤k≤12 is {4, 6, 8, 12, 15, 16}, the sum is 61.
What is the sum of all the minimal product-sum numbers for 2≤k≤12000?
题目：
一个自然数N如果能写成一个两个元素以上的集合， ，中元素的积与和的话，该数字被称为积和数：
例如：6 = 1 + 2 + 3 = 1 × 2 × 3.
对于一个大小为 k 的集合，我们将最小的具有该性质的数字 N 成为一个最小积和数。k = 2, 3, 4, 5, 6 的集合的最小积和数如下：
因此对于 2≤k≤6, 所有最小积和数的总和为 4+6+8+12 = 30；注意 8 在求和时只计算一次。
事实上对于 2≤k≤12，所有最小积和数的集合是 {4, 6, 8, 12, 15, 16}，其和为 61。
对于 2≤k≤12000，所有最小积和数的和是多少？
这题的思路是运用分解质因数，先把一个数分解成所有质因数。然后用1来补足不足的位数，如果补完后的和与原来相等，则找到积合数。
sum of minimal product-sum numbers: 7587457
max. number is 12200
import math
def factorize(n):
f = []
d = 2
bound = math.sqrt(n)
while d <= bound and n > 1:
if n % d == 0:
f.append(d)
n = n / d
else:
d = d + 1
if n > 1:
f.append(n)
return f
def factorizations(n):
f = factorize(n)
sol = set()
sol.add(tuple())
for p in f:
prev = sol
sol = set()
for pf in prev:
sol.add(tuple(sorted(pf + (p, ))))
t = list(pf)
for i in range(len(t)):
t *= p
sol.add(tuple(sorted(t)))
t /= p
return sol
kmax = 12000
mpsn = [ None ] * (kmax + 1)
rem = kmax - 1
n = 2
while rem > 0:
for nf in factorizations(n):
no = n - sum(nf) # number of ones
k = no + len(nf)
if k < 2 or k > kmax:
continue
elif mpsn is None:
mpsn = n
rem -= 1
n += 1
mpsns = set(mpsn)
print 'sum of minimal product-sum numbers:', sum(mpsns)
print 'max. number is', n - 1 mem = []
used = set()
k = set(range(2, 12001))
for n in range(9999999999999999):
mem.append(set())
if len(k) == 0:
break
for p in range(2, 999999999999999999999):
if p * p > n:
break
if n % p != 0:
continue
d = n // p
for i in mem:
mem.add(i + n - p - d + 1)
mem.add(1)
for i in mem:
if i in k:
k.remove(i)
used.add(n)
print(sum(used))
https://github.com/devinizz/project_euler/blob/master/page02/88.py /*
答案：7587456
耗时：0.671572秒
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 12000;//欲求的范围
const int M = 24000;//计算的范围
int k;//记录要求的结果
int fp;//fp记录i的最小素因数
int pc;//记录i的素因数个数
/*
对x进行分解为nc个因数的乘积
int nc 分解的因数个数
int x 要被分解的数
int nS 前面已经分解的因数和
vector<int> &v 记录整个分解的因数之和
*/
void dfs(int nc, int x, int nS, vector<int> &v)//递归计算分解
{
if (nc == 1)//分解结束
{
v.push_back(nS + x);
return;
}
if (fp == x)//x是素数无法分解
return;
for (int i = fp; i <= (int)sqrt((double)x); ++i)//枚举x的可能因数
{
if (x%i == 0)
dfs(nc - 1, x / i, nS + i, v);//继续下去
}
}
int main(void)
{
memset(k, -1, sizeof(k));//将k都预置为-1
//应用筛法求每个数的最小素数数
for (int i = 1; i < M; ++i)
fp = i;
for (int i = 2; i <= (int)sqrt((double)M); ++i)
{
if (fp < i)
continue;
for (int j = i*i; j < M; j += i)
fp = min(fp, i);
}
//计算每个数的素因数个数
for (int i = 2; i < M; ++i)
{
int x = i;
while (x > 1)
{
int y = fp;
x /= y;
++pc;
}
}
//计算k
for (int i = 4; i < M; ++i)
{
if (fp == i)//素数肯定不是和积数
continue;
for (int j = 2; j <= pc; ++j)
{
vector<int> v;
dfs(j, i, 0, v);//对i进行长度为j的因数分解
for (auto itr = v.begin(); itr != v.end(); ++itr)//对不同的分解计算k
{
int u = i - *itr;//计算积与和的差，补上上这些1就成了和积数
if (u >= 0 && u <= N)
{
u += j;//加上分解的长度
if (k < 0)
k = i;
else
k = min(k, i);
}
}
}
}
//排序和去重
sort(k, k + N + 1);
auto itr_end = unique(k, k + N + 1);
//求和
long long nSum = 0;
for (auto itr = k; itr != itr_end; ++itr)
nSum += *itr;
cout << nSum << endl;
return 0;
}
页:
[1]