Submission #3419338

---

Source Code Expand

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <vector>
//#include <array>
#include <set>
//#include <map>
//#include <unordered_set>
//#include <unordered_map>
//#include <stack>
#include <queue>
#include <numeric>
using ll = long long;
using namespace std;
using pdi = pair<double, int>;
unsigned int N;

#pragma once

#include <vector>

unsigned int mod;
struct Modint;
std::vector<Modint> fact_mod;
std::vector<Modint> rev_fact_mod;

using namespace std;

template<typename Tint>
Tint gcd(Tint a, Tint b) {
	// O(log max(a,b))
	return b != 0 ? gcd(b, a % b) : a;
}

template<typename Tint>
Tint lcm(Tint a, Tint b) {
	return a / gcd(a, b) * b;
}

// a x + b y = gcd(a, b)
int extgcd(const unsigned int a, const unsigned int b, int &x, int &y) {
	// O(log max(a,b))
	int g = a; x = 1; y = 0;
	if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
	return g;
}

void set_mod(const unsigned int m) {
	mod = m;
}
void set_mod(const int m) {
	if (m > 0)
		set_mod((unsigned int)m);
	else
		cout << "Error in set_mod" << endl;
}

unsigned int inv_mod(const unsigned int a) {
	int x, y;
	if (extgcd(a, mod, x, y) == 1)
		return (unsigned int)(((long long)x + mod) % mod);
	else // unsolvable
		return 0;
}

struct Modint {
	unsigned int value;
	Modint() : Modint(0) { }
	Modint(unsigned int value) : value(value%mod) {	}
	Modint(int value) : Modint((unsigned int)(value % mod + mod)) {	}
	Modint(const Modint& rhs) : Modint(rhs.value) { }
	Modint& operator+=(const Modint& rhs);
	Modint& operator+=(const unsigned int rhs);
	Modint& operator+=(const int rhs);
	Modint& operator-=(const Modint& rhs);
	Modint& operator-=(const unsigned int rhs);
	Modint& operator-=(const int rhs);
	Modint& operator*=(const Modint& rhs);
	Modint& operator*=(const unsigned int rhs);
	Modint& operator*=(const int rhs);
	Modint& operator/=(const Modint& rhs);
	Modint& operator/=(const unsigned int rhs);
	Modint& operator/=(const int rhs);
};
Modint& Modint::operator+=(const Modint& rhs)
{
	(*this) += rhs.value;
	return *this;
}
Modint& Modint::operator+=(const unsigned int rhs)
{
	unsigned long long tmp = this->value;
	tmp += rhs;
	tmp %= mod;
	this->value = (unsigned int)tmp;
	return *this;
}
Modint& Modint::operator+=(const int rhs)
{
	(*this) += (unsigned int)(rhs % mod + mod);
	return *this;
}
Modint& Modint::operator-=(const Modint& rhs)
{
	(*this) -= rhs.value;
	return *this;
}
Modint& Modint::operator-=(const unsigned int rhs)
{
	*this += mod - rhs % mod;
	return *this;
}
Modint& Modint::operator-=(const int rhs)
{
	*this -= (unsigned int)(rhs % mod + mod);
	return *this;
}
Modint& Modint::operator*=(const Modint& rhs)
{
	(*this) *= rhs.value;
	return *this;
}
Modint& Modint::operator*=(const unsigned int rhs)
{
	unsigned long long tmp = this->value;
	tmp *= rhs;
	tmp %= mod;
	this->value = (unsigned int)tmp;
	return *this;
}
Modint& Modint::operator*=(const int rhs)
{
	(*this) *= (unsigned int)(rhs % mod + mod);
	return *this;
}
Modint& Modint::operator/=(const Modint& rhs)
{
	(*this) /= rhs.value;
	return *this;
}
Modint& Modint::operator/=(const unsigned int rhs)
{
	*this *= inv_mod(rhs);
	return *this;
}
Modint& Modint::operator/=(const int rhs)
{
	*this /= (unsigned int)(rhs % mod + mod);
	return *this;
}
const Modint operator + (const Modint& lhs, const Modint& rhs) {
	return Modint(lhs) += rhs;
}
const Modint operator + (const Modint& lhs, unsigned int rhs) {
	return Modint(lhs) += rhs;
}
const Modint operator + (unsigned int lhs, const Modint& rhs) {
	return Modint(lhs) += rhs;
}
const Modint operator - (const Modint& lhs, const Modint& rhs) {
	return Modint(lhs) -= rhs;
}
const Modint operator - (const Modint& lhs, unsigned int rhs) {
	return Modint(lhs) -= rhs;
}
const Modint operator - (unsigned int lhs, const Modint& rhs) {
	return Modint(lhs) -= rhs;
}
const Modint operator * (const Modint& lhs, const Modint& rhs) {
	return Modint(lhs) *= rhs;
}
const Modint operator * (const Modint& lhs, unsigned int rhs) {
	return Modint(lhs) *= rhs;
}
const Modint operator * (unsigned int lhs, const Modint& rhs) {
	return Modint(lhs) *= rhs;
}
const Modint operator / (const Modint& lhs, const Modint& rhs) {
	return Modint(lhs) /= rhs;
}
const Modint operator / (const Modint& lhs, unsigned int rhs) {
	return Modint(lhs) /= rhs;
}
const Modint operator / (unsigned int lhs, const Modint& rhs) {
	return Modint(lhs) /= rhs;
}
ostream& operator<<(std::ostream& lhs, const Modint& rhs)
{
	lhs << rhs.value;
	return lhs;
}

Modint pow_mod(const Modint& x, const unsigned int k) { //x^k (mod)
	if (k == 0)     return Modint(1);
	if (k % 2 == 0) return pow_mod(x*x, k / 2);
	else            return x * pow_mod(x, k - 1);
}
Modint pow_mod(const unsigned int x, const unsigned int k) {
	return pow_mod(Modint(x), k);
}

std::vector<Modint> set_fact_mod(unsigned int n) {
	fact_mod = vector<Modint>(n + 1);
	fact_mod[0] = 1;
	for (unsigned int i = 1; i <= n; i++)
	{
		fact_mod[i] = fact_mod[i - 1] * i;
	}
	return fact_mod;
}

std::vector<Modint> set_rev_fact_mod(unsigned int n) {
	rev_fact_mod = vector<Modint>(n + 1);
	rev_fact_mod[n] = 1 / fact_mod[n];
	for (int i = n - 1; i >= 0; i--)
	{
		rev_fact_mod[i] = rev_fact_mod[i + 1] * (unsigned int)(i + 1);
	}
	return rev_fact_mod;
}

Modint combination_mod_precalculation(unsigned int n, unsigned int r) {
	//set mod, fact_mod, rev_fact_mod
	return fact_mod[n] * rev_fact_mod[r] * rev_fact_mod[n - r];
}

Modint combination_mod_straightforward(unsigned int n, unsigned int r) { //mod is prime
	if (r * 2 > n) r = n - r;
	Modint numerator = 1;
	Modint denominator = 1;
	for (unsigned int i = 1; i <= r; ++i) {
		numerator *= n - i + 1;
		denominator *= i;
	}
	return numerator / denominator;
}
#pragma once

#include <algorithm>
#include <vector>
#include <unordered_map>

std::vector<bool> is_primes;
std::vector<unsigned int> primes;

using namespace std;

void set_is_primes(unsigned int n) {
	//sieve_of_eratosthenes
	//is_primes : [0, n] の配列で，primes[i] = true iff i は素数
	//O(n log n)
	is_primes.assign(n + 1, true);
	for (unsigned int i = 0; i <= 1; ++i)
		is_primes[i] = false;
	for (unsigned int i = 2; i*i <= n; ++i)
		if (is_primes[i])
			for (unsigned int j = i * i; j <= n; j += i)
				is_primes[j] = false;
	return;
}

void set_primes(unsigned int n) {
	//sieve_of_eratosthenes
	//primes : n以下の素数のリスト
	//O(n log n)
	primes.assign(n + 1, 0);
	for (unsigned int i = 2; i <= n; ++i) primes[i] = i;
	for (unsigned int i = 2; i*i <= n; ++i)
		if (primes[i])
			for (unsigned int j = i * i; j <= n; j += i)
				primes[j] = 0;
	primes.erase(remove(primes.begin(), primes.end(), 0), primes.end());
	return;
}

vector<bool> make_is_prime_segments(unsigned long long L, unsigned long long H) {
	//区間ふるい
	//is_primes : [L, H] の配列で，primes[i] = true iff i は素数
	//O((H-L) sqrt( H ) / log(H))
	vector<bool> is_prime_segments(H - L + 1, true);
	for (int i = 0; (unsigned long long)primes[i] * primes[i] <= H; ++i) { // O( \sqrt(H) )
		unsigned long long j;
		if (primes[i] >= L)          j = primes[i] * primes[i];
		else if (L % primes[i] == 0) j = L;
		else                         j = L - (L % primes[i]) + primes[i];
		for (; j <= H; j += primes[i]) is_prime_segments[j - L] = false;
	}
	return is_prime_segments;
}

bool is_prime(const int n, const bool is_using_is_primes) {
	if (n <= 1)
		return false;
	for (int i = 2; i*i <= n; i++) {
		if (is_using_is_primes && !is_primes[i])
			continue;
		if (n % i == 0)
			return false;
	}
	return true;
}

vector<unsigned int> make_divisors(const unsigned int n) {
	vector<unsigned int> ans;
	for (unsigned int i = 1; i*i <= n; i++)
		if (n%i == 0)
			ans.emplace_back(i);
	vector<unsigned int> latter;
	const auto rit_b = ans.crbegin();
	const bool is_square = (*rit_b * *rit_b == n);
	for (auto rit = rit_b + (is_square ? 1 : 0), rit_e = ans.crend(); rit != rit_e; rit++)
		latter.emplace_back(n / *rit);
	ans.insert(ans.end(), latter.begin(), latter.end());
	return ans;
}

unordered_map<unsigned int, unsigned int> make_prime_factors(unsigned int n, const bool is_using_primes) {
	//O(sqrt(n))
	unordered_map<unsigned int, unsigned int> prime_factors;
	for (unsigned int i = 2; i*i <= n; i++) {
		if (is_using_primes && !is_primes[i])
			continue;
		while (n % i == 0) {
			++prime_factors[i];
			n /= i;
		}
	}
	if (n != 1)
		++prime_factors[n];
	return prime_factors;
}

int main() {
	cin >> N;
	unordered_map<unsigned int, unsigned int> um = make_prime_factors(N, false);
	for (const auto &e : um) {
		if (e.second > 1) {
			cout << -1 << endl;
			return 0;
		}
	}
	unsigned int period = 1;
	for (const auto &e : um) {
		period = lcm(period, e.first - 1);
	}
	unordered_map<unsigned int, unsigned int> um2 = make_prime_factors(period, false);
	unsigned int ans = 1;
	for (const auto &e : um2) {
		const unsigned int p = e.first;
		if (N%p == 0) {
			cout << -1 << endl;
			return 0;
		}
		const unsigned int e_p = e.second;
		const unsigned int q = (unsigned int)pow(p, e_p);
		const unsigned int phase_e = q / p * (p - 1);
		vector<unsigned int> divisors = make_divisors(phase_e);
		set_mod(q);
		for (const auto &divisor : divisors) {
			if (pow_mod(N, divisor).value == 1) {
				ans = lcm(ans, divisor);
				break;
			}
		}
	}
	cout << ans << endl;
}

Submission Info

Compile Error

./Main.cpp:20:9: warning: #pragma once in main file
 #pragma once
         ^
./Main.cpp:239:9: warning: #pragma once in main file
 #pragma once
         ^

Judge Result