Submission #495773

---

Source Code Expand

#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define all(x) begin(x),end(x)
#define REP(i,b,n) for(int i=static_cast<int>(b);i<static_cast<int>(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,(v).size())
using namespace std;

using Int = long long;
Int gcd(Int a, Int b){//{{{
    while(b) swap(a %= b, b);
    return a;
}//}}}
Int lcm(Int a, Int b){ return a / gcd(a, b) * b; }
Int powmod(Int b, Int e, Int m){//{{{
    Int res = 1;
    for(b %= m; e; e >>= 1, (b *= b) %= m) if(e&1) (res *= b) %= m;
    return res;
}//}}}
vector<Int> prime_factorization(Int n){//{{{
    vector<Int> res;
    for(Int p = 2; p <= n; ++p){
        if(p * p > n) p = n;
        for(; n % p == 0; n /= p) res.emplace_back(p);
    }
    return res;
}//}}}
vector<Int> divisiors(Int n){//{{{
    vector<Int> res;
    auto ps = prime_factorization(n);
    set<Int> pq; pq.emplace(1);
    while(!pq.empty()){
        auto m = *begin(pq); pq.erase(m);
        res.emplace_back(m);
        for(auto &p : ps) if(n % (m * p) == 0) pq.emplace(m * p);
    }
    return res;
}//}}}
Int lambda(Int n){//{{{
    Int res = 1;
    if(n % 8 == 0) n >>= 1;
    for(Int p = 2; p <= n; ++p){
        if(p * p > n) p = n;
        if(n % p != 0) continue;
        Int now = p-1;
        for(n /= p; n % p == 0; n /= p) now *= p;
        res = lcm(res, now);
    }
    return res;
}//}}}
Int ord(const Int &n, const Int &m){//{{{
    if(gcd(n, m) != 1) return 0;
    for(auto &d : divisiors(lambda(m))) if(powmod(n, d, m) == 1 % m) return d;
    assert(false);
    return 0;
}//}}}

int main(){//{{{
    Int n; cin >> n;
    auto ps = prime_factorization(n);
    Int res = 1;
    if(adjacent_find(begin(ps), end(ps)) != end(ps)) res = -1;
    else for(auto &p : ps) if(res) res = lcm(res, ord(n, p-1));
    cout << (res ? res : -1) << endl;
    return 0;
}//}}}
// vim:set foldmethod=marker commentstring=//%s:

Submission Info

Judge Result