费马的秘密遗物

在古老的阿尔法大陆，有一个被称为“费马的遗物”的神秘物品。据传闻，这个遗物是费马大师亲手制作的神秘计算器。阿尔法大陆的居民们相信，它可以预测未来、解决困境、甚至改变命运。但要启动这个神秘的遗物，需要快速求出密码，由于人力运算速度不够快，你希望能够借助计算机来快速完成计算。

现在给定三个正整数 a,b,p，其中 p 是一个质数，目的是求 a^bmod  p的值。成功计算出这个值可能是启动“费马的遗物”的关键。

输入格式

一行三个整数 a,b,p 。其中 1≤a,b≤10^9, 2≤p≤10^7 且 p 是质数。

输出格式

输出一个整数，表示 a^bmod  p的值。

样例输入

3 4 5

样例输出

1

这是著名的模平方指数算法。 

阶乘的和

问题描述

给定 nn 个数 AiA，问能满足 m!为∑i=1^n(Ai!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1×2×3×⋯×m。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数，分别表示 Ai​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

3
2 2 2

样例输出

3

int main() {
	int n;
	cin >> n;
	vector<long long> A(n);
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	long long min_val = A[0];
	map<long long, int> freq;
	for (long long num : A) {
		freq[num]++;
	}

	long long current = freq[min_val];
	long long i = min_val + 1;
	while (current % i == 0) {
		current /= i;
		if (freq.find(i) != freq.end()) {
			current += freq[i];
		}
		i++;
	}

	cout << i - 1 << endl;
	return 0;
}

避免直接计算m!的和。 

阶乘的位数

9 的阶乘等于：362880362880, 它的二进制表示为：1011000100110000000, 这个数字共有 1919 位。 请你计算，99999999 的阶乘的二进制表示一共有多少位？

•一个数n的二进制位数可以通过log2(n) + 1来， 9999！的二进制位数就是log2(9999!)+1。斯特林公式：n! ≈ √(2πn) * (n/e)^n，所以，log2(n!) ≈ log2(√(2πn)) + n * log2(n/e) ，更精确地：log2(n!) = (1/2) * log2(2πn) + n * log2(n) - n * log2(e) + O(1/n)近似等于118444.855， 

共有118445位。 

取模