c++ - Calculating the summation of powers of a number modulo a number -


there 3 numbers: t, n, m. 1 ≤ t, m ≤ 10^9, 1 ≤ n ≤ 10^18 .

what asked in problem compute [Σ(t^i)]mod(m) varies 0 n. obviously, o(n) or o(m) solutions wouldn't work because of 1 second time limit. how should proceed?

as pointed out in previous answers, may use formula geometric progression sum. there small problem - if m not prime, computing (t^n - 1) / (t - 1) can not done directly - division not well-defined operations. in fact there solution can handle non prime modules , have complexity o(log(n) * log(n)). approach similar binary exponentiation. here code written in c++ this(note solution uses binary exponentiation internally):

typedef long long ll; ll binary_exponent(ll x, ll y, ll mod) {   ll res = 1;    ll p = x;    while (y) {     if (y % 2) {        res = (res * p) % mod;      }         p = (p * p) % mod;      y /= 2;   }   return res;  }  ll gp_sum(ll a, int n, ll mod) {   ll = 1;    int num = 0;    ll res = 0;    ll degree = 1;    while (n) {     if (n & (1 << num)) {       n &= (~(1 << num));       res = (res + (a * binary_exponent(a, n, mod)) % mod) % mod;      }         = (a + (a * binary_exponent(a, degree, mod)) % mod) % mod;      degree *= 2;     num++;   }   return res;  } 

in solution a stores consecutively values 1, 1 + a, 1 + + a^2 + a^3, ...1 + + a^2 + ... ^ (2^n - 1).

also in binary exponentiation if want compute sum of n degrees of a, split n sum of powers of two(essentially using binary representation of n). having above sequence of values a, choose appropriate lengths(the ones correspond 1 bits of binary representation of n) , multiply sum value of a accumulating result in res. computing values of a take o(log(n)) time , each value may have compute degree of a result in o(log(n)) - overall have o(log(n) * log (n)).

let's take example - want compute 1 + + a^2 .... + ^ 10. in case, call gp_sum(a, 11, mod).

on first iteration n & (1 << 0) not 0 first bit of 11(1011(2)) 1. turn off bit setting n 10 , accumulate in res: 0 + 1 * (a ^ (10)) = a^10. a + 1.

the next second bit set in 10(1010(2)), n becomes 8 , res a^10 + (a + 1)*(a^8)=a^10 + a^9 + a^8. 1 + + a^2 + a^3

next bit 0, res stays same, become 1 + + a^2 + ... a^7.

on last iteration bit 1 have: res = a^10 + a^9 + a^8 + a^0 *(1 + + a^2 + ... +a^7) = 1 + .... + ^10.


Comments