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
Post a Comment