core.exception.OutOfMemoryError@(0) 使用大型动态数组
core.exception.OutOfMemoryError@(0) using a large dynamic array
import std.math;
import std.bigint;
import std.stdio;
BigInt sum_min_pfactor(long N){
BigInt f(int n) {
return BigInt(n)*(BigInt(n)+1) / 2 - 1;
}
int v = cast(int)(sqrt(float(N)));
bool[] used;
used.length = v+1;
BigInt ret;
BigInt finish;
BigInt[] s_sum,s_cnt,l_cnt,l_sum;
s_sum.length = v+1;
l_sum.length = v+1;
s_cnt.length = v+1;
l_cnt.length = v+1;
for (long i = 0; i <= v; i++) {
s_cnt[i] = i - 1;
s_sum[i] = f(cast(int)i);
}
for (long i = 1; i <= v; i++) {
l_cnt[i] = N / cast(int)i - 1;
l_sum[i] = f(cast(int)(N) / cast(int)i);
}
for (long p = 2; p <= v; p++) {
if (s_cnt[p] == s_cnt[p-1]) {
continue;
}
BigInt p_cnt = s_cnt[p-1];
BigInt p_sum = s_sum[p - 1];
long q = p * p;
ret = ret + p * (l_cnt[p] - p_cnt);
l_cnt[1] = l_cnt[1] - l_cnt[p] + p_cnt;
l_sum[1] = l_sum[1] - (l_sum[p] - p_sum) * p;
long interval = (p & 1) + 1;
if (v > N / q) {
finish = N / q;
}
else {
finish = v;
}
for (long i = p+interval; i <= finish; i += interval){
if (used[i]) {
continue;
}
long d = i * p;
if (d <= v) {
l_cnt[i] = l_cnt[i] - l_cnt[d] + p_cnt;
l_sum[i] = l_sum[i] - (l_sum[d] - p_sum) * p;
}
else {
long t = N / d;
l_cnt[i] = l_cnt[i] - s_cnt[t] + p_cnt;
l_sum[i] = l_sum[i] - (s_sum[t] - p_sum) * p;
}
}
if (q <= v) {
for (long i = q; i < finish; i += p*interval){
used[i] = true;
}
}
for (long i = v; i >= q - 1; i--) {
long t = i / p;
s_cnt[i] = s_cnt[i] - s_cnt[t] + p_cnt;
s_sum[i] = s_sum[i] - (s_sum[t] - p_sum) * p;
}
}
return l_sum[1] + ret;
}
void main () {
writeln(sum_min_pfactor(pow(10,12)));
}
上面的代码在处理小于 10^9 的数字时效果很好。但是,此后它开始给出不正确的值,并在尝试计算 10^9 的答案时因内存错误而崩溃。我正在使用 BigInt 库,但我的猜测是未声明为 BigInts 的变量之一弄乱了我的结果。我还假设内存错误是由动态数组的大小引起的,但我不知道如何解决该特定问题。
答案是 std.math.pow()
函数中的整数溢出。
的输出
writefln("%d", pow(10, 12));
writefln("%d", pow(10, 12L));
是
-727379968
1000000000000
现在 sqrt(-727379968)
是 -nan
。转换为整数得到 int.min
,大约是 -2 GiB。数组的 length
属性 是无符号的。因此每个数组的大小为 type.sizeof
* 2 GiB,这解释了内存不足的错误。
解决方法:给一个或两个数字加上后缀L,例如
writeln(sum_min_pfactor(pow(10L,9L)));
import std.math;
import std.bigint;
import std.stdio;
BigInt sum_min_pfactor(long N){
BigInt f(int n) {
return BigInt(n)*(BigInt(n)+1) / 2 - 1;
}
int v = cast(int)(sqrt(float(N)));
bool[] used;
used.length = v+1;
BigInt ret;
BigInt finish;
BigInt[] s_sum,s_cnt,l_cnt,l_sum;
s_sum.length = v+1;
l_sum.length = v+1;
s_cnt.length = v+1;
l_cnt.length = v+1;
for (long i = 0; i <= v; i++) {
s_cnt[i] = i - 1;
s_sum[i] = f(cast(int)i);
}
for (long i = 1; i <= v; i++) {
l_cnt[i] = N / cast(int)i - 1;
l_sum[i] = f(cast(int)(N) / cast(int)i);
}
for (long p = 2; p <= v; p++) {
if (s_cnt[p] == s_cnt[p-1]) {
continue;
}
BigInt p_cnt = s_cnt[p-1];
BigInt p_sum = s_sum[p - 1];
long q = p * p;
ret = ret + p * (l_cnt[p] - p_cnt);
l_cnt[1] = l_cnt[1] - l_cnt[p] + p_cnt;
l_sum[1] = l_sum[1] - (l_sum[p] - p_sum) * p;
long interval = (p & 1) + 1;
if (v > N / q) {
finish = N / q;
}
else {
finish = v;
}
for (long i = p+interval; i <= finish; i += interval){
if (used[i]) {
continue;
}
long d = i * p;
if (d <= v) {
l_cnt[i] = l_cnt[i] - l_cnt[d] + p_cnt;
l_sum[i] = l_sum[i] - (l_sum[d] - p_sum) * p;
}
else {
long t = N / d;
l_cnt[i] = l_cnt[i] - s_cnt[t] + p_cnt;
l_sum[i] = l_sum[i] - (s_sum[t] - p_sum) * p;
}
}
if (q <= v) {
for (long i = q; i < finish; i += p*interval){
used[i] = true;
}
}
for (long i = v; i >= q - 1; i--) {
long t = i / p;
s_cnt[i] = s_cnt[i] - s_cnt[t] + p_cnt;
s_sum[i] = s_sum[i] - (s_sum[t] - p_sum) * p;
}
}
return l_sum[1] + ret;
}
void main () {
writeln(sum_min_pfactor(pow(10,12)));
}
上面的代码在处理小于 10^9 的数字时效果很好。但是,此后它开始给出不正确的值,并在尝试计算 10^9 的答案时因内存错误而崩溃。我正在使用 BigInt 库,但我的猜测是未声明为 BigInts 的变量之一弄乱了我的结果。我还假设内存错误是由动态数组的大小引起的,但我不知道如何解决该特定问题。
答案是 std.math.pow()
函数中的整数溢出。
writefln("%d", pow(10, 12));
writefln("%d", pow(10, 12L));
是
-727379968
1000000000000
现在 sqrt(-727379968)
是 -nan
。转换为整数得到 int.min
,大约是 -2 GiB。数组的 length
属性 是无符号的。因此每个数组的大小为 type.sizeof
* 2 GiB,这解释了内存不足的错误。
解决方法:给一个或两个数字加上后缀L,例如
writeln(sum_min_pfactor(pow(10L,9L)));