結果

問題 No.3038 フィボナッチ数列の周期
ユーザー toriaezuACtoriaezuAC
提出日時 2018-04-03 22:30:41
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 17,684 bytes
コンパイル時間 985 ms
コンパイル使用メモリ 118,440 KB
最終ジャッジ日時 2023-09-08 15:33:53
合計ジャッジ時間 1,372 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:31:9: エラー: ‘size_t’ does not name a type
   31 |         size_t size() const;
      |         ^~~~~~
main.cpp:5:1: 備考: ‘size_t’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
    4 | #include <map>
  +++ |+#include <cstddef>
    5 | 
main.cpp:147:8: エラー: no declaration matches ‘size_t FactoredExpression::size() const’
  147 | size_t FactoredExpression::size() const {
      |        ^~~~~~~~~~~~~~~~~~
main.cpp:147:8: 備考: no functions named ‘size_t FactoredExpression::size() const’
main.cpp:7:7: 備考: ‘class FactoredExpression’ defined here
    7 | class FactoredExpression {
      |       ^~~~~~~~~~~~~~~~~~
main.cpp: 関数 ‘ULL Period(ULL, ULL)’ 内:
main.cpp:553:31: エラー: ‘const class FactoredExpression’ has no member named ‘size’
  553 |         const int N = factors.size();
      |                               ^~~~

ソースコード

diff # 

#ifndef __FACTORIZATION_H__
#define __FACTORIZATION_H__

#include <map>

/* 正整数を素数指数表現で表す (分数は未対応 → GCD などの計算量が変わるため) */
class FactoredExpression {
	typedef unsigned long long ULong;
	typedef std::map<ULong, int> List;
	typedef List::const_iterator const_iterator;

	List list_m;			// 素因数とそれに対する指数の組
public:
	FactoredExpression();
	FactoredExpression(const FactoredExpression& other);
	FactoredExpression& operator=(const FactoredExpression& other);

	FactoredExpression& operator*=(const FactoredExpression& right);
	FactoredExpression& operator/=(const FactoredExpression& right);
	FactoredExpression& operator&=(const FactoredExpression& right);	// LCM
	FactoredExpression& operator|=(const FactoredExpression& right);	// GCD

	int Get_exponent_of(ULong factor) const;
	void Set_exponent_of(ULong factor, int exponent);
	void Increase_exponent_of(ULong factor, int exponent_increment);

	ULong To_integer() const;
	
	const_iterator begin() const;
	const_iterator end() const;
	size_t size() const;
};

FactoredExpression operator*(const FactoredExpression& left, const FactoredExpression& right);
FactoredExpression operator/(const FactoredExpression& left, const FactoredExpression& right);
FactoredExpression operator&(const FactoredExpression& left, const FactoredExpression& right);
FactoredExpression operator|(const FactoredExpression& left, const FactoredExpression& right);

FactoredExpression Factorize(unsigned long long value);
unsigned long long Pow(unsigned long long base, unsigned int exponent);

#endif

#include <algorithm>
#include <cassert>

FactoredExpression::FactoredExpression()
	: list_m() {
}

FactoredExpression::FactoredExpression(const FactoredExpression& other)
	: list_m(other.list_m) {
}

FactoredExpression& FactoredExpression::operator=(const FactoredExpression& other) {
	list_m = other.list_m;
	return *this;
}

FactoredExpression& FactoredExpression::operator*=(const FactoredExpression& right) {
	for (const_iterator it = right.begin(); it != right.end(); ++it) {
		const ULong factor = it->first;
		const int exponent = it->second;

		list_m[factor] += exponent;
	}
	return *this;
}

FactoredExpression& FactoredExpression::operator/=(const FactoredExpression& right) {
	for (const_iterator it = right.begin(); it != right.end(); ++it) {
		const ULong factor = it->first;
		const int exponent = it->second;

		/* TODO: 高速化 */
		assert((list_m[factor] -= exponent) >= 0);
		if (list_m[factor] == 0) {
			list_m.erase(factor);
		}
	}
	return *this;
}

/* GCD */
FactoredExpression& FactoredExpression::operator&=(const FactoredExpression& right) {
	for (const_iterator it = begin(); it != end(); ) {		// it は自身の iterator なので注意
		const ULong factor = it->first;
		const int exponent = it->second;

		/* TODO: 高速化 */
		list_m[factor] = std::min(exponent, right.Get_exponent_of(factor));
		++it;		// erase すると iterator が使えなくなるのでここでインクリメントする
		if (list_m[factor] == 0) {
			list_m.erase(factor);
		}
	}
	return *this;
}

/* LCM */
FactoredExpression& FactoredExpression::operator|=(const FactoredExpression& right) {
	for (const_iterator it = right.begin(); it != right.end(); ++it) {
		const ULong factor = it->first;
		const int exponent = it->second;

		/* TODO: 高速化 */
		list_m[factor] = std::max(list_m[factor], exponent);
	}
	return *this;
}

int FactoredExpression::Get_exponent_of(ULong factor) const {
	List::const_iterator it = list_m.find(factor);
	if (it == list_m.end()) return 0;

	return it->second;
}

void FactoredExpression::Set_exponent_of(ULong factor, int exponent) {
	assert(exponent >= 0);
	list_m[factor] = exponent;
}

void FactoredExpression::Increase_exponent_of(ULong factor, int exponent_increment) {
	assert((list_m[factor] += exponent_increment) >= 0);
}

FactoredExpression::ULong FactoredExpression::To_integer() const {
	ULong ret = 1;
	for (const_iterator it = begin(); it != end(); ++it) {
		const ULong factor = it->first;
		const int exponent = it->second;

		ret *= Pow(factor, exponent);
	}
	return ret;
}

FactoredExpression::const_iterator FactoredExpression::begin() const {
	return list_m.begin();
}

FactoredExpression::const_iterator FactoredExpression::end() const {
	return list_m.end();
}

size_t FactoredExpression::size() const {
	return list_m.size();
}

FactoredExpression operator*(const FactoredExpression& left, const FactoredExpression& right) {
	FactoredExpression ret(left);
	ret *= right;
	return ret;
}

FactoredExpression operator/(const FactoredExpression& left, const FactoredExpression& right) {
	FactoredExpression ret(left);
	ret /= right;
	return ret;
}

FactoredExpression operator&(const FactoredExpression& left, const FactoredExpression& right) {
	FactoredExpression ret(left);
	ret &= right;
	return ret;
}

FactoredExpression operator|(const FactoredExpression& left, const FactoredExpression& right) {
	FactoredExpression ret(left);
	ret |= right;
	return ret;
}

/* 素因数分解をして素数指数表記に変換する O(sqrt(value)) */
FactoredExpression Factorize(unsigned long long value) {
	FactoredExpression ret;

	for (unsigned long long i = 2; i * i <= value; ++i) {
		/* 割り切れるだけ i で割る */
		int count = 0;
		while (value % i == 0) {
			value /= i;
			++count;
		}

		if (count != 0) {
			ret.Set_exponent_of(i, count);
		}
	}

	/* sqrt(value) 以下の数で割って割り切れないなら、それは素数 */
	if (value != 1) {
		ret.Set_exponent_of(value, 1);
	}

	return ret;
}

unsigned long long Pow(unsigned long long base, unsigned int exponent) {
	if (exponent == 0) return 1;
	if (exponent % 2 == 1) return base * Pow(base, exponent - 1);
	unsigned long long tmp = Pow(base, exponent / 2);
	return tmp * tmp;
}
#ifndef __INTMOD_H__0001__
#define __INTMOD_H__0001__

#include <vector>
#include <iostream>
#include <cassert>
#include <iostream>

/* Modulus must be less than 0x80000000, and not be 0. */
template <uint32_t Modulus>
class IntMod {
	typedef int Int;
	typedef unsigned int UInt;
	typedef long long Long;
	typedef unsigned long long ULong;

public:
	template <uint32_t Modulus_>
	friend bool operator==(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator!=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator<(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator<=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator>(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator>=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);

private:
	UInt value_m;

public:
	IntMod() { value_m = 0; }
	IntMod(UInt value) { value_m = value % Modulus; }
	IntMod(ULong value) { value_m = value % Modulus; }
	IntMod(Int value) {
		Int tmp = value % (Int)Modulus;
		value_m = tmp >= 0 ? tmp : Modulus - (unsigned int)(-tmp);
	}
	IntMod(Long value) {
		Int tmp = value % (Long)Modulus;
		value_m = tmp >= 0 ? tmp : Modulus - (unsigned int)(-tmp);
	}
	IntMod(const IntMod& other) : value_m(other.value_m) {}
	IntMod& operator=(const IntMod& other) { value_m = other.value_m; return *this; }
	
	const IntMod& operator+() const { return *this; }
	IntMod operator-() const { return IntMod(Modulus - value_m); }
	IntMod& operator++() {
		++value_m;
		if (value_m == Modulus) value_m = 0;
		return *this;
	}
	IntMod& operator--() {
		if (value_m == 0) value_m = Modulus;
		--value_m;
		return *this;
	}
	IntMod operator++(int dummy) {
		IntMod tmp(*this);
		++(*this);
		return tmp;
	}
	IntMod operator--(int dummy) {
		IntMod tmp(*this);
		--(*this);
		return tmp;
	}
	IntMod& operator+=(const IntMod& right) {
		value_m += right.value_m;		// value_m < 0x80000000
		if (value_m >= Modulus) value_m -= Modulus;
		return *this;
	}
	IntMod& operator-=(const IntMod& right) {
		if (value_m < right.value_m) value_m += Modulus;
		value_m -= right.value_m;
		return *this;
	}
	IntMod& operator*=(const IntMod& right) {
		value_m = ((ULong)value_m * right.value_m) % Modulus;
		return *this;
	}	
	IntMod& operator/=(const IntMod& right) {
		(*this) *= (right.Inverse());
		return *this;
	}
	// for power
	IntMod operator[](ULong exp) const {
		return Pow(exp);
	}

	/* Modulus must be a prime. */
	IntMod Inverse() const { return (*this).Pow(Modulus - 2); }
	IntMod Pow(ULong exp) const {
		IntMod product = 1;
		IntMod factor(*this);
		while (exp > 0) {
			if (exp & 1) product *= factor;
			factor *= factor;
			exp >>= 1;
		}
		return product;
	}
	UInt Get_value() const {
		return value_m;
	}

	static IntMod Fact(UInt num) {
		static std::vector<IntMod> table(1, 1);
		if (table.size() > num) return table[num];

		int old_size = table.size();
		table.resize(num + 1);
		for (int i = old_size; i <= num; i++) {
			table[i] = table[i - 1] * i;
		}
		return table[num];
	}

	static IntMod Combi(UInt n, UInt r) {
		if (n < r) throw "okashii";
		return IntMod::Fact(n) / (IntMod::Fact(n - r) * IntMod::Fact(r));
	}

	static std::vector<IntMod> Inverse_list(int size) {
		assert(size < Modulus);
		std::vector<IntMod> ret_arr(size + 1);
		ret_arr[1] = 1;
		for (int i = 2; i <= size; ++i) {
			ret_arr[i] = ((ULong)(Modulus - Modulus / i) * ret_arr[Modulus % i].Get_value()) % Modulus;
		}
		return ret_arr;
	}
};

template <uint32_t Modulus>
IntMod<Modulus> operator+(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret += right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator-(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret -= right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator*(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret *= right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator/(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret /= right;
	return ret;
}


template <uint32_t Modulus>
bool operator==(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m == right.value_m; }
template <uint32_t Modulus>
bool operator!=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m != right.value_m; }
/* for set/map */
template <uint32_t Modulus>
bool operator<(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m < right.value_m; }
template <uint32_t Modulus>
bool operator<=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m <= right.value_m; }
template <uint32_t Modulus>
bool operator>(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m > right.value_m; }
template <uint32_t Modulus>
bool operator>=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m >= right.value_m; }

template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator+(const IntMod<Modulus>& left, Integer right) { return left + IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator+(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) + right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator-(const IntMod<Modulus>& left, Integer right) { return left - IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator-(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) - right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator*(const IntMod<Modulus>& left, Integer right) { return left * IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator*(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) * right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator/(const IntMod<Modulus>& left, Integer right) { return left / IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator/(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) / right; }

template <uint32_t Modulus>
std::istream& operator<<(std::istream& ist, const IntMod<Modulus>& val) {
	uint64_t tmp;
	ist >> tmp;
	val = tmp;
	return ist;
}

template <uint32_t Modulus>
std::ostream& operator<<(std::ostream& ost, const IntMod<Modulus>& val) {
	ost << val.Get_value();
	return ost;
}

typedef IntMod<1000000007> MInt;

#if 1
MInt operator"" _m(unsigned long long num) { return MInt(num); }
#endif

#endif

#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i, a, n) for(LL i = (a), i##_max = (n); i < i##_max; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##min = (a); i >= i##min; --i)
#define ALL(arr) (arr).begin(), (arr).end()
#define FLOAT fixed << setprecision(16)
#define SPEEDUP {cin.tie(NULL); ios::sync_with_stdio(false);}
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const string INFSTR = "\x7f";
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }
template <class T>
T Next() { T buf; cin >> buf; return buf; }

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Union_Find.h"
#include "Graph.h"
#include "Range.h"
#include "Global.h"
#include "Flow_Solver.h"
#include "Tree.h"
#include "Suffix_Array.h"
#include "Geometry.h"
#include "Matrix.h"
#include "Segment_Tree.h"
#include "Rational.h"
#include "Position.h"
#include "Factorization.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
template <class T>
auto Is(const T& value) { return [value](const auto& comparand) -> bool { return comparand == value; }; }
#endif

struct Mat {
	ULL a, b, c, d;
};

Mat operator*(const Mat& p, const Mat& q) {
	return {
		p.a * q.a + p.b * q.c,
		p.a * q.b + p.b * q.d,
		p.c * q.a + p.d * q.c,
		p.c * q.b + p.d * q.d
	};
}

Mat operator%(const Mat& p, ULL mod) {
	return {
		p.a % mod,
		p.b % mod,
		p.c % mod,
		p.d % mod
	};
}

Mat Pow(const Mat& p, ULL exp, ULL mod) {
	if (exp == 0) return Mat{ 1, 0, 0, 1 };
	if (exp % 2 == 1) return p * Pow(p, exp - 1, mod) % mod;
	Mat tmp = Pow(p, exp / 2, mod);
	return tmp * tmp % mod;
}

bool Is_unit(const Mat& p) {
	return p.a == 1 && p.b == 0 && p.c == 0 && p.d == 1;
}

ULL Period(ULL mod, ULL expected_period) {
	const auto& factors = Factorize(expected_period);
	const int N = factors.size();
	
	const Mat fib_gene = Mat{ 1, 1, 1, 0 };


	ULL mn = 0xffffffffffffffff;
	vector<int> curr(N, 0);
	while (curr[0] <= factors.begin()->second) {
		Mat product = fib_gene;
		auto fit = factors.begin();
		for (int i = 0; i < N; ++i, ++fit) {
			for (int j = 0; j < curr[i]; ++j) {
				product = Pow(product, fit->first, mod);
			}
		}

		if (Is_unit(product)) {
			ULL ans = 1;
			auto it = factors.begin();
			for (int i = 0; i < N; ++i, ++it) {
				ans *= Pow(it->first, curr[i]);
			}
			mn = min(mn, ans);
		}

		++curr.back();
		auto it = prev(factors.end());
		for (int i = N - 1; i > 0 && curr[i] > it->second; --i, --it) {
			curr[i] = 0;
			++curr[i - 1];
		}
	}
	return mn;
}

int main() {
	int N;
	cin >> N;

	MInt ans = 1;
	FactoredExpression lcm;

	for (int i = 0; i < N; ++i) {
		ULL p, k;
		cin >> p >> k;

		ULL period;
		if (p == 2) {
			period = 3;
		} else if (p == 5) {
			period = 20;
		} else {
			ULL r = p * p % 5;
			ULL expected_period = (r == 1 ? p - 1 : 2 * p + 2);
			period = Period(p, expected_period);
		}

		auto fe = Factorize(period);
		fe.Increase_exponent_of(p, k - 1);
		lcm |= fe;
	}

	for (auto p : lcm) {
		ans *= MInt(p.first)[p.second];
	}

	cout << ans << endl;
	return 0;
}
0