Участник:Easik/KPOWERSUM

Материал из DISCOPAL
Перейти к: навигация, поиск

[Не проходит по времени] Задача проходит кейс, но не проходит по времени (TLE, которое указано справа как 1s, хотя ещё в июле решения людей проходили с временем 1.44s: https://www.spoj.com/ranks/KPOWERSUM/start=40)

C \ gcc

Другие компиляторы тоже пробовал, но TLE.

#include <stdio.h>
#include <stdlib.h>
 
#define S       1 << 22
#define MODULO  1000000007
 
long long N;
int T, K, primeCount;
int lp[S], primelist[S];
 
int inverse(int a);
int power(int a, int b);
 
 
int main() {
 
    int i, j;
    int c, d;
    int result;
    int invProduct;
    int base, numerator;
 
    for (i = 2; i < S; i++) {
 
        if (!lp[i]) {
 
            primelist[++primeCount] = i;
            lp[i] = i;
 
        }
 
        for (j = 1; (j <= primeCount) && (primelist[j] <= lp[i]) && (i * primelist[j] < S); j++) {
 
            lp[i * primelist[j]] = primelist[j];
 
        }
 
    }
 
    scanf("%d", &T);
 
    for (c = 0; c < T; c++) {
 
        scanf("%lld %d", &N, &K);
 
        result = 1;
        invProduct = 1;
        for (i = 1; i <= primeCount; i++) {
 
            if (1LL * primelist[i] * primelist[i] > N) {
 
                break;
 
            }
 
            if (N % primelist[i] == 0) {
 
                d = 0;
                while (N % primelist[i] == 0) {
 
                    d++;
                    N /= primelist[i];
 
                }
 
                base = power(primelist[i], K);
                numerator = power(base, d + 1) - 1;
                invProduct = 1LL * invProduct * (base - 1) % MODULO;
                result = 1LL * result * numerator % MODULO;
 
            }
 
        }
 
        if (N > 1) {
 
            base = power(N % MODULO, K);
            numerator = 1LL * base * base % MODULO - 1;
            invProduct = 1LL * invProduct * (base - 1) % MODULO;
            result = 1LL * result * numerator % MODULO;
 
        }
 
        result = 1LL * result * inverse(invProduct) % MODULO;
 
        printf("Case %d: %d\n\n", c + 1, result);
 
    }
 
    return 0;
 
}
 
 
int power(int a, int b) {
 
    int result = 1;
    int p = a;
 
    while (b) {
 
        if (b & 1) {
 
            result = 1LL * result * p % MODULO;
 
        }
 
        b >>= 1;
        p = 1LL * p * p % MODULO;
 
    }
 
    return result;
 
}
 
 
int inverse(int a) {
 
    return power(a, MODULO - 2);
 
}