Number Theory and Binary Search

Description

• Topics : Number Theory, Binary Search
• Link to the contest

Editorial

caution

Don’t read the editorial, if you have not attempted or read the problems. It would hamper your thinking capability, if you do so.

A. Find $x^{F(n)}$ mod m

Problem

Given 3 positive integers - $x$, $n$ and $m$. Find value of $x^{F(n)}$ mod $m$ .
The function $F(n)$ is defined as the product of square of primes up to $n$ (inclusive).
For eg. $F(5) = 2^2 \cdot 3^2 \cdot 5^2 = 900$ .

Constraints

• $1 \leq x,m \leq 10^9$
• $2 \leq n \leq 10^6$

Editorial

Since $n \leq 10^6$, we need to use sieve of Erasthoneses to find out all the prime numbers from 1 to $n$ in $O(n\cdot\log(\log n))$.

Also, one could easily observe that the value of $F(n)$ would definitely overflow for larger values of $n$. So, we can't find $F(n)$ directly.

Here, we can use the property $a^{b \cdot c} = {(a^b)}^c$ . For finding ${a^b} \bmod m$ , use binary exponentation, which works in $O(\log_2 b)$ .

Final time complexity: $O(n \log_2 n)$

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX = 1e6;

int modulo(int a, int b, int n) {
    // Binar exponentation to calculate a^b in O(log b)
  int x = 1, y = a;
  while (b > 0) {
    if (b % 2 == 1) {
      x = (x * y) % n;
    }
    y = (y * y) % n;
    b /= 2;
  }
  return x % n;
}



int32_t main() {
  int x, n, m;
  cin >> x >> n >> m;
  sieve();  // pre-compute all the primes

  int prod = x;  // final answer would be stored in prod

  for (int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prod = modulo(prod, i, m);
      prod = modulo(prod, i, m);
      // Use the property (a^b)^c = a^(b*c).
      // Since, directly calculating F(n) first will overflow
    }
  }
  cout << prod;
  return 0;
}