Submission #2337369


Source Code Expand

#include<bits/stdc++.h>
 
using namespace std;
 
template< typename T = long long >
T pow_mod(T x, T n, T mod)
{
  T ret = 1;
  while(n > 0) {
    if(n & 1) ret = 1LL * ret * x % mod;
    x = 1LL * x * x % mod;
    n >>= 1;
  }
  return ret;
}
 
int lcm(int x, int y)
{
  return (x / __gcd(x, y) * y);
}
 
map< int, int > primefactor(int x)
{
  map< int, int > ret;
  for(int i = 2; i * i <= x; i++) {
    while(x % i == 0) {
      ret[i]++;
      x /= i;
    }
  }
  if(x != 1) ret[x]++;
  return (ret);
}
 
int lambda(int x)
{
  auto pp = primefactor(x);
  vector< int > vs;
  for(auto &p : pp) {
    if(p.first == 2) {
      if(p.second <= 2) vs.push_back(p.second);
      else vs.push_back(1 << (p.second - 2));
    } else {
      int cur = 1;
      for(int i = 1; i < p.second; i++) cur *= p.first;
      cur *= p.first - 1;
      vs.push_back(cur);
    }
  }
  int ret = vs[0];
  for(int i : vs) ret = lcm(ret, i);
  return (ret);
}
 
vector< int > beet(int x)
{
  vector< int > vs;
  for(int i = 1; i * i <= x; i++) {
    if(x % i == 0) {
      if(i * i != x) vs.push_back(x / i);
      vs.push_back(i);
    }
  }
  sort(begin(vs), end(vs));
  return (vs);
}
 
int solve(int N)
{
  if(N == 2) return (1);
  auto latte = lambda(N);
  for(auto &s : beet(lambda(latte))) {
    if(pow_mod(N, s, latte) == 1) return (s);
  }
  return (-1);
}
 
 
int main()
{
  int N;
  cin >> N;
  cout << solve(N) << endl;
}

Submission Info

Submission Time
Task D - Identity Function
User ei13333
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1494 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 83
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 20_mini_00, 20_mini_01, 20_mini_02, 20_mini_03, 20_mini_04, 20_mini_05, 20_mini_06, 20_mini_07, 20_mini_08, 20_mini_09, 20_mini_10, 20_mini_11, 20_mini_12, 20_mini_13, 20_mini_14, 20_mini_15, 20_mini_16, 20_mini_17, 20_mini_18, 20_mini_19, 30_square_00, 30_square_01, 30_square_02, 30_square_03, 30_square_04, 30_square_05, 30_square_06, 30_square_07, 30_square_08, 30_square_09, 30_square_10, 30_square_11, 30_square_12, 30_square_13, 30_square_14, 30_square_15, 30_square_16, 30_square_17, 30_square_18, 30_square_19, 40_maxrandom_00, 40_maxrandom_01, 40_maxrandom_02, 40_maxrandom_03, 40_maxrandom_04, 40_maxrandom_05, 40_maxrandom_06, 40_maxrandom_07, 40_maxrandom_08, 40_maxrandom_09, 40_maxrandom_10, 40_maxrandom_11, 40_maxrandom_12, 40_maxrandom_13, 40_maxrandom_14, 40_maxrandom_15, 40_maxrandom_16, 40_maxrandom_17, 40_maxrandom_18, 40_maxrandom_19, 50_impossible_00, 50_impossible_01, 50_impossible_02, 50_impossible_03, 50_impossible_04, 50_impossible_05, 50_impossible_06, 50_impossible_07, 50_impossible_08, 50_impossible_09, 60_biganswer_00, 60_biganswer_01, 60_biganswer_02, 60_biganswer_03, 60_biganswer_04, 60_biganswer_05, 60_biganswer_06, 60_biganswer_07, 60_biganswer_08, 60_biganswer_09
Case Name Status Exec Time Memory
00_sample_00 AC 1 ms 256 KB
00_sample_01 AC 1 ms 256 KB
00_sample_02 AC 1 ms 256 KB
20_mini_00 AC 1 ms 256 KB
20_mini_01 AC 1 ms 256 KB
20_mini_02 AC 1 ms 256 KB
20_mini_03 AC 1 ms 256 KB
20_mini_04 AC 1 ms 256 KB
20_mini_05 AC 1 ms 256 KB
20_mini_06 AC 1 ms 256 KB
20_mini_07 AC 1 ms 256 KB
20_mini_08 AC 1 ms 256 KB
20_mini_09 AC 1 ms 256 KB
20_mini_10 AC 1 ms 256 KB
20_mini_11 AC 1 ms 256 KB
20_mini_12 AC 1 ms 256 KB
20_mini_13 AC 1 ms 256 KB
20_mini_14 AC 1 ms 256 KB
20_mini_15 AC 1 ms 256 KB
20_mini_16 AC 1 ms 256 KB
20_mini_17 AC 1 ms 256 KB
20_mini_18 AC 1 ms 256 KB
20_mini_19 AC 1 ms 256 KB
30_square_00 AC 1 ms 256 KB
30_square_01 AC 1 ms 256 KB
30_square_02 AC 1 ms 256 KB
30_square_03 AC 1 ms 256 KB
30_square_04 AC 1 ms 256 KB
30_square_05 AC 1 ms 256 KB
30_square_06 AC 1 ms 256 KB
30_square_07 AC 1 ms 256 KB
30_square_08 AC 1 ms 256 KB
30_square_09 AC 1 ms 256 KB
30_square_10 AC 1 ms 256 KB
30_square_11 AC 1 ms 256 KB
30_square_12 AC 1 ms 256 KB
30_square_13 AC 1 ms 256 KB
30_square_14 AC 1 ms 256 KB
30_square_15 AC 1 ms 256 KB
30_square_16 AC 1 ms 256 KB
30_square_17 AC 1 ms 256 KB
30_square_18 AC 1 ms 256 KB
30_square_19 AC 1 ms 256 KB
40_maxrandom_00 AC 1 ms 256 KB
40_maxrandom_01 AC 1 ms 256 KB
40_maxrandom_02 AC 1 ms 256 KB
40_maxrandom_03 AC 1 ms 256 KB
40_maxrandom_04 AC 1 ms 256 KB
40_maxrandom_05 AC 1 ms 256 KB
40_maxrandom_06 AC 1 ms 256 KB
40_maxrandom_07 AC 1 ms 256 KB
40_maxrandom_08 AC 1 ms 256 KB
40_maxrandom_09 AC 1 ms 256 KB
40_maxrandom_10 AC 1 ms 256 KB
40_maxrandom_11 AC 1 ms 256 KB
40_maxrandom_12 AC 1 ms 256 KB
40_maxrandom_13 AC 1 ms 256 KB
40_maxrandom_14 AC 1 ms 256 KB
40_maxrandom_15 AC 1 ms 256 KB
40_maxrandom_16 AC 1 ms 256 KB
40_maxrandom_17 AC 1 ms 256 KB
40_maxrandom_18 AC 1 ms 256 KB
40_maxrandom_19 AC 1 ms 256 KB
50_impossible_00 AC 1 ms 256 KB
50_impossible_01 AC 1 ms 256 KB
50_impossible_02 AC 1 ms 256 KB
50_impossible_03 AC 1 ms 256 KB
50_impossible_04 AC 1 ms 256 KB
50_impossible_05 AC 1 ms 256 KB
50_impossible_06 AC 1 ms 256 KB
50_impossible_07 AC 1 ms 256 KB
50_impossible_08 AC 1 ms 256 KB
50_impossible_09 AC 1 ms 256 KB
60_biganswer_00 AC 1 ms 256 KB
60_biganswer_01 AC 1 ms 256 KB
60_biganswer_02 AC 1 ms 256 KB
60_biganswer_03 AC 1 ms 256 KB
60_biganswer_04 AC 1 ms 256 KB
60_biganswer_05 AC 1 ms 256 KB
60_biganswer_06 AC 1 ms 256 KB
60_biganswer_07 AC 1 ms 256 KB
60_biganswer_08 AC 1 ms 256 KB
60_biganswer_09 AC 1 ms 256 KB