给定 n
,我想找到一个数 i
,使得 phi(i) = n
。其中,n <= 100,000,000
。
当 n = 99683840
时,i
的最大值为 202918035
。我想解决 this problem。
我的方法是预先计算所有小于最大值 i
的数的欧拉函数值。
我使用埃拉托斯特尼筛法找出所有小于最大值 i
的质数,并在筛法过程中记录这些质数的欧拉函数值。
然后使用
phi
数组中搜索输入数字并将结果打印到输出。
但是这会导致时间限制超出。
预计算中还可以进一步优化什么,或者有更好的方法来做到这一点吗?我的代码是:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
int* Prime = (int*)malloc(sizeof(int) * (202918036 >> 5 + 1));
int* pos = (int*)malloc(sizeof(int) * (11231540));
int* phi = (int*)malloc(sizeof(int) * 202918036);
#define prime(i) ((Prime[i >> 5]) & (1 << (i & (31))))
#define set(j) (Prime[j >> 5] |= (1 << (j & (31))))
#define LIM 202918035
#define SLIM 14245
int sieve() {
int i, j, m, n, t, x, k, l, h;
set(1);
phi[0] = 0;
phi[1] = 0;
pos[1] = 2;
phi[2] = 1;
pos[2] = 3;
phi[3] = 2;
for (k = 2, l = 3, i = 5; i <= SLIM; k++, i = 3 * k - (k & 1) - 1)
if (prime(k) == 0) {
pos[l++] = i;
phi[i] = i - 1;
for (j = i * i, h = ((j + 2) / 3); j <= LIM; h += (k & 1) ? (h & 1 ? ((k << 2) - 3) : ((k << 1) - 1)) : (h & 1 ? ((k << 1) - 1) : ((k << 2) - 1)), j = 3 * h - (h & 1) - 1)
set(h);
}
i = 3 * k - (k & 1) - 1;
for (; i <= LIM; k++, i = 3 * k - (k & 1) - 1)
if (prime(k) == 0) {
pos[l++] = i;
phi[i] = i - 1;
}
return l;
}
int ETF() {
int i;
for (i = 4; i < LIM; i++) {
if (phi[i] == 0) {
for (int j = 1; j < i; j++) {
if (i % pos[j] == 0) {
int x = pos[j];
int y = i / x;
if (y % x == 0) {
phi[i] = x * phi[y];
} else {
phi[i] = phi[x] * phi[y];
}
break;
}
}
}
}
}
int search(int value) {
for (int z = 1; z < LIM; z++) {
if (phi[z] == value) return z;
}
return -1;
}
int main() {
int m = sieve();
int t;
ETF();
scanf("\n%d", &t);
while (t--) {
int n;
scanf("%d", &n);
if (n % 2 == 1) {
printf("-1\n");
} else {
int i;
i = search(n);
if (i == -1) printf("-1\n");
else printf("%d\n", i);
}
}
return 0;
}
n * log(n) * log(log(n))
的东西。 - Andreas Grapentinn
,以消除歧义。 - Daniel Fischer