Блог пользователя jash2703

Seive function

Автор jash2703, история, 2 месяца назад, По-английски

Can any one solve this

C++ code N^(f(X)) mod M

f(X) is defined as product of primes upto X

1<=N,M<=10^9

1<=X<=10^6

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

For any $$$a, b$$$ and $$$c$$$, $$$(a^b)^c = a^{bc}$$$. So,

int ans = n;
for (int p : primes)
  ans = pow(ans, p, m);

where pow is implemented using fast exponentiation.

→ Ответить