Оптимизация алгоритма

Question

Задача link.

Проблема задает число решений уравнения диофантовой вида 1/х + 1/у = 1/г (где г = п!). Перестановка данного уравнения ясно говорит о том, что ответом является число факторов z.

Так проблема кипит, чтобы найти количество факторов n!.

Мой алгоритм выглядит следующим образом

1. Сделать булево посмотреть таблицу для всех простых чисел < = п с помощью решета Эратосфена алгоритма.
2. Iterate все простые числа P < = п и найти свой показатель в п!. Я сделал это, используя формулу функции шага. Пусть показатель равен K, тогда показатель P в n! будет 2K.
3. Используя шаг 2, вычислите количество факторов со стандартной формулой.

Для наихудшего случая ввода п = 10, мой с код дает ответ в 0.056s. Я предполагаю, что сложность не превосходит O (n lg n). Но когда я отправил код на сайт, я мог бы пройти только 3/15 тестовых случаев с приговором остальных, поскольку превышен лимит времени.

Мне нужна подсказка для оптимизации этого алгоритма.

код до сих пор:

#include <stdio.h> 
#include <string.h> 

#define ULL unsigned long long int 
#define MAXN 1000010 
#define MOD 1000007 

int isPrime[MAXN]; 

ULL solve(int N) { 
    int i, j, f; 
    ULL res = 1; 
    memset(isPrime, 1, MAXN * sizeof(int)); 
    isPrime[0] = isPrime[1] = 0; 
    for (i = 2; i * i <= N; ++i) 
     if (isPrime[i]) 
      for (j = i * i; j <= N; j += i) 
       isPrime[j] = 0; 
    for (i = 2; i <= N; ++i) { 
     if (isPrime[i]) { 
      for (j = i, f = 0; j <= N; j *= i) 
       f += N/j; 
      f = ((f << 1) + 1) % MOD; 
      res = (res * f) % MOD; 
     } 
    } 
    return res % MOD; 
} 

int main() { 
    int N; 
    scanf("%d", &N); 
    printf("%llu\n", solve(N)); 
    return 0; 
} 

Answer 1

У вас есть int переполнения здесь:

for (j = i, f = 0; j <= N; j *= i) 

Если 46340 < i < 65536 и для многих больше i, во второй итерации j будут отрицательными, если переполнение обтекает (это неопределенное поведение, так что все может случиться).

Заменить его, например.

for(j = N/i, f = 0; j > 0; j /= i) { 
    f += j; 
} 

Это, однако, маловероятно, что дополнительные итерации из-за переполнения приведет к «лимит времени превышается», что, скорее всего, только вызвать неправильные результаты.

Так общий совет

• Сито только нечетные числа, возможно, также исключить кратные 3 из решета.Устранение нечетных чисел из сита приблизительно вдвое увеличивает время, необходимое для решеток.
• Не используйте целые int для флагов, используйте биты или не менее char s. Это дает лучшую локальность кэша и дальнейшее ускорение.