倒数欧拉函数

Question

倒数欧拉函数

c++calgorithm

5

给定 n，我想找到一个数 i，使得 phi(i) = n。其中，n <= 100,000,000。当 n = 99683840 时，i 的最大值为 202918035。我想解决 this problem。

我的方法是预先计算所有小于最大值 i 的数的欧拉函数值。我使用埃拉托斯特尼筛法找出所有小于最大值 i 的质数，并在筛法过程中记录这些质数的欧拉函数值。然后使用

enter image description here

然后我在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;
}

- Gaurav Deshmukh

你的程序筛选质数需要多久时间？（在输入之前）（我猜这不应该是个问题 - 如果我正确理解了你的代码，你使用2、3为基础进行轮式筛法，并使用位表示是否为质数）。 - nhahtdh

注意：通常有许多解决方案。对于任何k > 1，存在n使得phi(x) = n恰好有k个解（对于k = 1，这样的n不存在是Carmichael猜想）。 - Alexandre C.

我记得用一种从不低估的近似函数做过类似这样的事情。我想那大概是类似于 n * log(n) * log(log(n)) 的东西。 - Andreas Grapentin

@AlexandreC。在这种情况下，希望找到最小的n，以消除歧义。 - Daniel Fischer

你可能会对这个感兴趣：http://www.new.dli.ernet.in/rawdataupload/upload/insa/INSA_2/20005a81_22.pdf - 这里提供了一个看起来很有效的算法，可以实现你想要完成的任务。 - IVlad

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

这是一个HTML标签。

     for(int j=1;j<i;j++)
     {            
        if(i%pos[j]==0)
        {

这段内容是关于IT技术的，它讲解了一种试除法来寻找i的最小质因数。这使得算法的时间复杂度为O(n^2/log^2 n)，因为不超过n的质数约有n/log n个，对于一个质数i，您会测试所有不超过i的质数。

如果您使用筛法来查找最小[或任何]质因数，则可以获得更快的算法（虽然我怀疑它是否足够快）。这是埃拉托斯特尼筛法的简单修改，不仅标记数字为合成数，而且将质数存储为该数字的因子。在用每个数字的质因数填充筛子后，您可以像以前一样计算欧拉函数。

phi[i] = p*phi[i/p]

如果 p² 可以整除 i 或者

phi[i] = (p-1)*phi[i/p]

如果它没有。

使用该方法计算欧拉函数是一个 O(n*log n) 的算法[也许甚至是 O(n*log log n)，我还没有详细分析过]。

此外，您的搜索

int search(int value) {
    for (int z = 1; z < LIM; z++) {
        if (phi[z] == value) return z;
    }
    return -1;
}

非常缓慢。您可以创建一个查找表以实现O(1)的查找。