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 |
|
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 |