fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int eulerPhi(int X) {
  5.     int i = 2;
  6.     int q, ret = X;
  7.  
  8.     while (1LL * i * i <= X) {
  9.         q = X / i;
  10.  
  11.         if (X == i * q) {
  12.             do {
  13.                 X = q;
  14.                 q = X / i;
  15.             } while (X == i * q);
  16.  
  17.             ret = (ret / i) * (i - 1);
  18.         }
  19.         i++;
  20.     }
  21.  
  22.     if (X != 1) {
  23.         ret = ret / X * (X - 1);
  24.     }
  25.     return ret;
  26. }
  27.  
  28. int lgPut(int A, int B, int MOD) {
  29.     int Q = 1;
  30.     while (B) {
  31.         if (B & 1) {
  32.             Q = (1LL * Q * A) % MOD;
  33.         }
  34.         A = (1LL * A * A) % MOD;
  35.         B >>= 1;
  36.     }
  37.     return Q;
  38. }
  39.  
  40. int solve(int A, int MOD) {
  41.     if (MOD == 1) {
  42.         return 0;
  43.     }
  44.     if (A == 1) {
  45.         return 1;
  46.     }
  47.     return lgPut(A, solve(A - 1, eulerPhi(MOD)), MOD);
  48. }
  49.  
  50. int main() {
  51. 	int N, M;
  52. 	scanf("%d%d", &N, &M);
  53. 	printf("%d\n", solve(N, M));
  54. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5 123456789
stdout
copy 
16317634
https://ideone.com/vvH4jS
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!