Переполнение с мощностью

Question

Если я вычисляю [x * (a^b)% mod + y% mod]% mod, если я просто использую (a^b)% mod, умножил бы это на x, давая мне правильный ответ ? Не будет ли вычисление (x * (a^b))% mod пошагово, лучше? Просто пытаюсь оправдать себя, почему бы не включить x работает. Что можно сделать?

Answer 1

Попробуйте этот код. Идея состоит в том, чтобы вводить новые функции для модульного сложения, умножения и возведения в степень:

#define MOD 1000000007 

inline int modadd(int a, int b) { 
    return ((long long)a + b) % MOD; 
} 

inline int modmult(int a, int b) { 
    return ((long long) a * b) % MOD; 
} 

inline unsigned modexp(unsigned base, unsigned exp) 
{ 
    unsigned result = 1; 
    while (exp > 0) { 
     if (exp & 1) result = ((unsigned long long)result * base) % MOD; 
     base = ((unsigned long long)base * base) % MOD; 
     exp >>= 1; 
    } 
    return result; 
} 

int main(void) 
{ 
    unsigned A[3] = {1, 2, 3}; 
    unsigned r[3]; 
    unsigned i, n = 3; 

    r[0] = 0; 
    r[1] = modmult(2, A[0]); 
    for (i = 1; i < n; i++) { 
     r[i+1] = modadd(r[i], modmult(A[i], modexp(2, i))); 
    } 
}