Submission #2559962

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

long long N, C = 1; vector<long long>R;

long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

int main() {
	cin >> N;
	for (int i = 2; i*i <= N; i++) {
		if (N%i == 0) {
			N /= i; R.push_back(i);
			if (N%i == 0) { cout << "-1" << endl; return 0; }
		}
	}
	if (N >= 2) { R.push_back(N); }
	if (R.size() <= 1) { cout << "1" << endl; return 0; }
	if (R.size() >= 3 || R[0] == 2) { cout << "-1" << endl; return 0; }
	long long a = R[0], b = R[1], c = 1, s = -1, t = -1;
	for (int i = 1; i <= b / 2; i++) {
		c *= a; c %= (b - 1);
		if (c == 1) { s = i; break; }
	}
	c = 1;
	for (int i = 1; i <= a / 2; i++) {
		c *= b; c %= (a - 1);
		if (c == 1) { t = i; break; }
	}
	if (s == -1 || t == -1) { cout << "-1" << endl; }
	else { cout << s*t / gcd(s, t) << endl; }
	return 0;
}

Submission Info

Judge Result