jash2703's blog

Seive function

By jash2703, history, 4 months ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply