5

与えられnた、私はそのような私を見つけたいですphi(i) = n。n <= 100,000,000. の最大値i = 202918035 for n = 99683840。この問題を解決したい

私のアプローチは、すべての数値の totient 関数を maximum まで事前に計算すること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;
}
4

1 に答える 1

2

これ

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

iは、試行分割によっての最小の素因数を見つけていることを意味します。を超えない素数がO(n^2/log^2 n)約 あり、素数については、を超えないすべての素数をテストします。n/log nnii

ふるいを使用して最小の [または任意の] 素因数を見つければ、はるかに高速なアルゴリズムを取得できます (ただし、十分に高速であるとは思えません)。これはエラトステネスのふるいを単純に修正したもので、単に数値を合成としてマークするのではなく、素数をその数値の因数として保存します。各数の素因数でふるいを満たした後、次のいずれかのように totient を計算できます。

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

p²分割する場合iまたは

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

そうでない場合。

そのメソッドを使用して totients を計算することは、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) ルックアップを取得するためのルックアップ テーブルを作成できます。

于 2013-01-26T18:59:11.877 に答える