MMOD29 - CALCULATE POW(2004,X) MOD 29

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

using namespace std;

int powMod(int a, int p) {
  if (p == 1) return a % 29;
  int x = powMod(a, p >> 1);
  x = x * x % 29;
  if (p & 1) return x * a % 29;
  return x;
}

int cnt[2004];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("MMOD29.in", "r", stdin);
  #endif // _LAD_
  int power;
  while (cin >> power) {
    if (power == 0) break;
    int x = 2004;
    RESET(cnt, 0);
    for (int i = 2; i <= x; ++i)
    while (x % i == 0) {
      cnt[i] += power;
      x /= i;
    }
    int ans = 1;
    FOR(i, 2, 2004)
    if (cnt[i]) {
      ans = ans * (powMod(i, cnt[i] + 1) + 28) * powMod(i - 1, 27) % 29;
    }
    cout << ans << endl;
  }
  return 0;
}

Download