ACM模板

根据给定文件的信息，我们可以总结出以下几个重要的ACM算法模板知识点： ### 1. 埃拉托斯特尼筛法 埃拉托斯特尼筛法（Sieve of Eratosthenes），是一种用于查找所有小于或等于给定整数n的素数的高效算法。 #### 实现原理 该算法的基本思想是从最小的素数2开始，将其所有的倍数标记为合数（非素数），然后找到下一个未被标记为合数的数，并重复这一过程，直到遍历到n为止。 #### 示例代码解析 ```cpp int prime[maxn]; // 用于存储素数 bool is_prime[maxn]; // 用于标记数字是否为素数 int sieve(int n) { int p = 0; for (int i = 0; i <= n; ++i) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; ++i) { // 遍历每个数字 if (is_prime[i]) { // 如果当前数字未被标记，则它是素数 prime[p++] = i; // 将素数存入数组 for (int j = i + i; j <= n; j += i) // 轻剪枝：从i的倍数开始标记 is_prime[j] = false; } } return p; // 返回素数的个数 } ``` ### 2. 快速幂算法 快速幂算法是计算幂的一种高效方法，尤其适用于大数幂的计算。 #### 实现原理 快速幂算法的核心思想是将指数进行二进制分解，通过不断地平方操作和选择性地乘以基数来减少计算次数。 #### 示例代码解析 ```cpp typedef long long LL; // 使用长整型以避免溢出 LL powerMod(LL x, LL n, LL m) { LL res = 1; while (n > 0) { if (n & 1) // 如果n为奇数，则将结果乘以x res = (res * x) % m; x = (x * x) % m; // 平方操作 n >>= 1; // 相当于n除以2 } return res; } ``` ### 3. 大数模拟算法 在计算机编程竞赛中，经常需要处理超出常规数据类型所能表示范围的大数问题。 #### 大数加法实现 大数加法可以通过字符串模拟实现，将两个大数转换成字符串形式进行逐位相加并处理进位。 #### 示例代码解析 ```cpp string add1(string s1, string s2) { if (s1 == "" && s2 == "") return "0"; if (s1 == "") return s2; if (s2 == "") return s1; string maxx = s1, minn = s2; if (s1.length() < s2.length()) { maxx = s2; minn = s1; } int a = maxx.length() - 1, b = minn.length() - 1; for (int i = b; i >= 0; --i) { maxx[a--] += minn[i] - '0'; } for (int i = maxx.length() - 1; i > 0; --i) { if (maxx[i] > '9') { maxx[i] -= 10; maxx[i - 1]++; } } if (maxx[0] > '9') { maxx[0] -= 10; maxx = '1' + maxx; } return maxx; } ``` #### 大数阶乘实现 大数阶乘同样可以通过数组模拟实现，逐步累乘每一个数字，并处理好每一位的进位。 #### 示例代码解析 ```cpp const int maxn = 100010; int num[maxn], len; void Init() { len = 1; num[0] = 1; } int mult(int num[], int len, int n) { long long tmp = 0; for (long long i = 0; i < len; ++i) { tmp += num[i] * n; num[i] = tmp % 10; tmp /= 10; } while (tmp) { num[len++] = tmp % 10; tmp /= 10; } return len; } int main() { Init(); int n = 1977; // 求n!的值 for (int i = 2; i <= n; ++i) { len = mult(num, len, i); // 求i!的结果 } // 输出结果 for (int i = len - 1; i >= 0; --i) { cout << num[i]; } return 0; } ``` 以上就是从给定文件中提取出的主要知识点，这些算法模板在ACM竞赛中非常实用，能够帮助参赛者快速解决问题。