fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6. using i64 = int64_t;
  7. using u32 = uint32_t;
  8. using u64 = uint64_t;
  9. using u128 = __uint128_t;
  10. template <typename T>
  11. T inverse(T a, T m)
  12. {
  13. 	T u = 0, v = 1;
  14. 	while (a != 0)
  15. 	{
  16. 		T t = m / a;
  17. 		m -= t * a;
  18. 		swap(a, m);
  19. 		u -= t * v;
  20. 		swap(u, v);
  21. 	}
  22. 	assert(m == 1);
  23. 	return u;
  24. }
  25.  
  26. template <typename T>
  27. class Modular
  28. {
  29. public:
  30. 	using Type = typename decay<decltype(T::value)>::type;
  31.  
  32. 	constexpr Modular() : value() {}
  33. 	template <typename U>
  34. 	Modular(const U &x)
  35. 	{
  36. 		value = normalize(x);
  37. 	}
  38.  
  39. 	template <typename U>
  40. 	static Type normalize(const U &x)
  41. 	{
  42. 		Type v;
  43. 		if (-mod() <= x && x < mod())
  44. 			v = static_cast<Type>(x);
  45. 		else
  46. 			v = static_cast<Type>(x % mod());
  47. 		if (v < 0)
  48. 			v += mod();
  49. 		return v;
  50. 	}
  51.  
  52. 	const Type &operator()() const { return value; }
  53. 	template <typename U>
  54. 	explicit operator U() const { return static_cast<U>(value); }
  55. 	constexpr static Type mod() { return T::value; }
  56.  
  57. 	Modular &operator+=(const Modular &other)
  58. 	{
  59. 		value += other.value;
  60. 		value -= (value >= mod()) * mod();
  61. 		return *this;
  62. 	}
  63. 	Modular &operator-=(const Modular &other)
  64. 	{
  65. 		value -= other.value;
  66. 		value += (value < 0) * mod();
  67. 		return *this;
  68. 	}
  69. 	template <typename U>
  70. 	Modular &operator+=(const U &other) { return *this += Modular(other); }
  71. 	template <typename U>
  72. 	Modular &operator-=(const U &other) { return *this -= Modular(other); }
  73. 	Modular &operator++() { return *this += 1; }
  74. 	Modular &operator--() { return *this -= 1; }
  75. 	Modular operator++(int)
  76. 	{
  77. 		Modular result(*this);
  78. 		*this += 1;
  79. 		return result;
  80. 	}
  81. 	Modular operator--(int)
  82. 	{
  83. 		Modular result(*this);
  84. 		*this -= 1;
  85. 		return result;
  86. 	}
  87. 	Modular operator-() const { return Modular(-value); }
  88.  
  89. 	template <typename U = T>
  90. 	typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type &operator*=(const Modular &rhs)
  91. 	{
  92. 		value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
  93. 		return *this;
  94. 	}
  95. 	template <typename U = T>
  96. 	typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type &operator*=(const Modular &rhs)
  97. 	{
  98. 		int64_t q = int64_t(static_cast<long double>(value) * rhs.value / mod());
  99. 		value = normalize(value * rhs.value - q * mod());
  100. 		return *this;
  101. 	}
  102. 	template <typename U = T>
  103. 	typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &operator*=(const Modular &rhs)
  104. 	{
  105. 		value = normalize(value * rhs.value);
  106. 		return *this;
  107. 	}
  108.  
  109. 	Modular &operator/=(const Modular &other) { return *this *= Modular(inverse(other.value, mod())); }
  110.  
  111. 	friend const Type &abs(const Modular &x) { return x.value; }
  112.  
  113. 	template <typename U>
  114. 	friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);
  115.  
  116. 	template <typename U>
  117. 	friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
  118.  
  119. 	template <typename V, typename U>
  120. 	friend V &operator>>(V &stream, Modular<U> &number);
  121.  
  122. private:
  123. 	Type value;
  124. };
  125.  
  126. template <typename T>
  127. bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value == rhs.value; }
  128. template <typename T, typename U>
  129. bool operator==(const Modular<T> &lhs, U rhs) { return lhs == Modular<T>(rhs); }
  130. template <typename T, typename U>
  131. bool operator==(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) == rhs; }
  132.  
  133. template <typename T>
  134. bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) { return !(lhs == rhs); }
  135. template <typename T, typename U>
  136. bool operator!=(const Modular<T> &lhs, U rhs) { return !(lhs == rhs); }
  137. template <typename T, typename U>
  138. bool operator!=(U lhs, const Modular<T> &rhs) { return !(lhs == rhs); }
  139.  
  140. template <typename T>
  141. bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value < rhs.value; }
  142.  
  143. template <typename T>
  144. Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }
  145. template <typename T, typename U>
  146. Modular<T> operator+(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) += rhs; }
  147. template <typename T, typename U>
  148. Modular<T> operator+(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }
  149.  
  150. template <typename T>
  151. Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }
  152. template <typename T, typename U>
  153. Modular<T> operator-(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
  154. template <typename T, typename U>
  155. Modular<T> operator-(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }
  156.  
  157. template <typename T>
  158. Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }
  159. template <typename T, typename U>
  160. Modular<T> operator*(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
  161. template <typename T, typename U>
  162. Modular<T> operator*(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }
  163.  
  164. template <typename T>
  165. Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }
  166. template <typename T, typename U>
  167. Modular<T> operator/(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
  168. template <typename T, typename U>
  169. Modular<T> operator/(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }
  170.  
  171. template <typename T, typename U>
  172. Modular<T> power(const Modular<T> &a, const U &b)
  173. {
  174. 	assert(b >= 0);
  175. 	Modular<T> x = a, res = 1;
  176. 	U p = b;
  177. 	while (p > 0)
  178. 	{
  179. 		if (p & 1)
  180. 			res *= x;
  181. 		x *= x;
  182. 		p >>= 1;
  183. 	}
  184. 	return res;
  185. }
  186.  
  187. template <typename T>
  188. bool IsZero(const Modular<T> &number)
  189. {
  190. 	return number() == 0;
  191. }
  192.  
  193. template <typename T>
  194. string to_string(const Modular<T> &number)
  195. {
  196. 	return to_string(number());
  197. }
  198.  
  199. // U == std::ostream? but done this way because of fastoutput
  200. template <typename U, typename T>
  201. U &operator<<(U &stream, const Modular<T> &number)
  202. {
  203. 	return stream << number();
  204. }
  205.  
  206. // U == std::istream? but done this way because of fastinput
  207. template <typename U, typename T>
  208. U &operator>>(U &stream, Modular<T> &number)
  209. {
  210. 	typename common_type<typename Modular<T>::Type, int64_t>::type x;
  211. 	stream >> x;
  212. 	number.value = Modular<T>::normalize(x);
  213. 	return stream;
  214. }
  215.  
  216. // using ModType = int;
  217.  
  218. // struct VarMod
  219. // {
  220. //     static ModType value;
  221. // };
  222. // ModType VarMod::value;
  223. // ModType &md = VarMod::value;
  224. // using Mint = Modular<VarMod>;
  225.  
  226. constexpr int md = 1e9 + 7;
  227. using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
  228.  
  229. template <int Rows, int Cols>
  230. class Matrix
  231. {
  232. private:
  233. 	Mint data[Rows][Cols];
  234.  
  235. public:
  236. 	// Constructor: zero matrix
  237. 	Matrix() { memset(data, 0, sizeof(data)); }
  238.  
  239. 	Matrix(Mint initValue)
  240. 	{
  241. 		for (int i = 0; i < Rows; i++)
  242. 			for (int j = 0; j < Cols; j++)
  243. 				data[i][j] = initValue;
  244. 	}
  245.  
  246. 	// Constructor: from 2D vector
  247. 	Matrix(const vector<vector<Mint>> &matrix)
  248. 	{
  249. 		assert(matrix.size() == Rows && (matrix.empty() || matrix[0].size() == Cols));
  250. 		for (int i = 0; i < Rows; i++)
  251. 			for (int j = 0; j < Cols; j++)
  252. 				data[i][j] = matrix[i][j];
  253. 	}
  254.  
  255. 	// Copy constructor
  256. 	Matrix(const Matrix &other) = default;
  257.  
  258. 	// Assignment operator
  259. 	Matrix &operator=(const Matrix &other) = default;
  260.  
  261. 	// Element access using operator[]
  262. 	Mint (&operator[](int row))[Cols]
  263. 	{
  264. 		assert(row >= 0 && row < Rows);
  265. 		return data[row];
  266. 	}
  267.  
  268. 	const Mint (&operator[](int row) const)[Cols]
  269. 	{
  270. 		assert(row >= 0 && row < Rows);
  271. 		return data[row];
  272. 	}
  273.  
  274. 	// Matrix multiplication
  275. 	template <int Q>
  276. 	Matrix<Rows, Q> operator*(const Matrix<Cols, Q> &other) const
  277. 	{
  278. 		Matrix<Rows, Q> result;
  279. 		for (int i = 0; i < Rows; i++)
  280. 		{
  281. 			for (int j = 0; j < Q; j++)
  282. 			{
  283. 				for (int k = 0; k < Cols; k++)
  284. 					result[i][j] += data[i][k] * other[k][j];
  285. 			}
  286. 		}
  287. 		return result;
  288. 	}
  289.  
  290. 	// Static method: create identity matrix
  291. 	template <int Size>
  292. 	static Matrix<Size, Size> createIdentity()
  293. 	{
  294. 		Matrix<Size, Size> identity;
  295. 		for (int i = 0; i < Size; i++)
  296. 			identity[i][i] = 1;
  297. 		return identity;
  298. 	}
  299. 	// Matrix exponentiation (only for square matrices)
  300. 	Matrix<Rows, Rows> matrixPower(ll exp) const
  301. 	{
  302. 		static_assert(Rows == Cols, "Matrix must be square for exponentiation");
  303. 		assert(exp >= 0);
  304.  
  305. 		Matrix<Rows, Rows> result = createIdentity<Rows>();
  306. 		Matrix<Rows, Rows> base = *this;
  307.  
  308. 		while (exp > 0)
  309. 		{
  310. 			if (exp & 1)
  311. 				result = result * base;
  312. 			base = base * base;
  313. 			exp >>= 1;
  314. 		}
  315. 		return result;
  316. 	}
  317.  
  318. 	// Input stream operator
  319. 	friend istream &operator>>(istream &is, Matrix &matrix)
  320. 	{
  321. 		for (int i{}; i < Rows; i++)
  322. 			for (int j{}; j < Cols; j++)
  323. 				is >> matrix[i][j];
  324. 		return is;
  325. 	}
  326. };
  327. constexpr int sz = 2;
  328. using TransMatrix = Matrix<sz, sz>;
  329.  
  330. void primeFactorize(ll N, map<ll, ll> &primeFactors)
  331. {
  332. 	while (!(N & 1))
  333. 		primeFactors[2]++, N >>= 1;
  334. 	for (ll i{3}; i * i <= N; i += 2)
  335. 	{
  336. 		while (N % i == 0)
  337. 			primeFactors[i]++, N /= i;
  338. 	}
  339. 	if (N > 1) // N is prime
  340. 		primeFactors[N]++;
  341. }
  342.  
  343. int main()
  344. {
  345. 	ios_base::sync_with_stdio(false);
  346. 	cin.tie(nullptr);
  347. #ifndef ONLINE_JUDGE
  348. 	freopen("input.txt", "r", stdin);
  349. 	freopen("Output.txt", "w", stdout);
  350. #endif //! ONLINE_JUDGE
  351. 	int t = 1;
  352. 	cin >> t;
  353. 	while (t--)
  354. 	{
  355. 		ll n, k;
  356. 		cin >> n >> k;
  357. 		map<ll, ll> primeFactors;
  358. 		primeFactorize(k, primeFactors);
  359. 		TransMatrix mat;
  360. 		Mint res = 1;
  361. 		for (const auto &[p, e] : primeFactors)
  362. 		{
  363. 			auto base = Matrix<2, 2>({{1, 1}, {e, 0}});
  364. 			auto T = base.matrixPower(n - 1);
  365. 			Mint A = T[0][0] + T[1][0];
  366. 			Mint B = T[0][1] + T[1][1];
  367. 			res *= (A + B * e);
  368. 		}
  369. 		cout << res << endl;
  370. 	}
  371. 	return 0;
  372. }
  373.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
648549718
https://ideone.com/gRzyia
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!