下载文档原格式
poj 1325 Machine Schedule(最小点覆盖->二分图最大匹配)题意：有两台机器A和B，分别有n种和m种不同的模式，有k个工作，每个工作都可以在那两个机器的某种特定的模式下处理。
如job0既可以在A机器的3好模式下处理，也可以在B 机器的4号模式下处理。
机器的工作模式改变只能通过人工来重启。
通过改变工作的顺序，和分配每个工作给合适的机器可以减少重启机器的次数达到最小。
任务就是计算那个最小的次数。
初始时两台机器都运行在0号模式下。
思路：把每个任务化为一条线，假设任务i在A机器上处理的模式为A［x]点，在B机器上为B［y]点，连接A[x]和B[y],用A机器和B机器中最少的点覆盖所有的边（用最少的模式完成所有的任务）。
这是最小点覆盖问题，根据König定理（一个二分图中的最大匹配数等于这个图中的最小点覆盖数）就是求的二分图的最大匹配，然后再用匈牙利算法直接就算出最大匹配数了，要注意的是初始是在0号模式下，所以如果A或B机器其中至少有个在0号模式下时就不用重启机器了，所以建图的时候没有把0建进去。
关于二分匹配在/u3/102624/showart.php?id=2060232#include <stdio.h>#include <string.h>#define N 105#define M 1005int g[N][N];int used[N], mat[N], flag[N];int min, n, m;/*寻找增广路径*/int find(int k){int i, j;for(i=1; i<=g[k][0]; i++){j = g[k][i];if(!used[j]){used[j] = 1;if(mat[j]==-1 || find(mat[j])){mat[j] = k;return 1;}}}return 0;}/*匈牙利算法*/void hungary(){int i;for(i=1; i<=n-1; i++){min += find(i);memset(used, 0, sizeof(used));}printf("%d\n", min);}int main(){int i, j;int k, a, b, c;while(scanf("%d", &n) && n){scanf("%d%d", &m, &k);memset(mat, -1, sizeof(mat));memset(g, 0, sizeof(g)); //一开始这个没有初始化，wa了好多次，搞好久==!for(i=0; i<k; i++){scanf("%d%d%d", &a, &b, &c);if(b != 0 && c != 0){g[b][++g[b][0]] = c; //邻接表}}min = 0;hungary();}}poj 1469 COURSES二分匹配问题：匈牙利算法实现（可以作为模板）//二分匹配中，两个集合不能存在交集#include <iostream>#include <string.h>#include <stdio.h>using namespace std;#define array1 101#define array2 301bool map[array1][array2]; //定义临界矩阵int final[array2];int match[array2];int p,n; //两个集合分别存储p个元素和n个元素int DFS(int p) //p为课程{int i;int t;//遍历所有的学生for(i=1;i<n+1;++i){if(map[p][i] && !final[i]){final[i] = 1;t= match[i];match[i]= p; //路径取反操作(原来在匹配中的边变成不在匹配中，不在的变成在每一次)if(t==0 || DFS(t)) return 1; //找到了一条增广路径match[i] = t;}}return 0; //没有找到增广路径}int mat(){int matchmax = 0; //matchmax为最大匹配数//遍历所有的课程for(i=1;i<p+1;++i){memset(final,0,sizeof(final)); //重新标记未访问,此处要注意if(DFS(i)) matchmax++;}return matchmax;}int main(){//freopen("1.txt","r",stdin);int t;int i,j,k;int temptcount;int stu;scanf("%d",&t);for(i=0;i<t;++i){memset(map,0,sizeof(map)); //对临界矩阵进行初始化memset(match,0,sizeof(match));scanf("%d%d",&p,&n);for(j=1;j<p+1;++j){scanf("%d",&temptcount);for(k=0;k<temptcount;++k){scanf("%d",&stu);map[j][stu] = 1;}}if(mat()==p) printf("YES\n");else printf("NO\n");}return 0;}POJ 2195 Going Home二分图最佳匹配，经典的KM算法#include <stdio.h>#include <string.h>const int MAXN = 200+5;const int INF = 1000000000;int N;int g[MAXN][MAXN];int pre[MAXN];int lx[MAXN], ly[MAXN], slack[MAXN],man[MAXN][2],ff[MAXN][2]; bool visx[MAXN], visy[MAXN];int abs(int a){if(a<0)return -a;return a;}bool dfs(int t){int i;visx[t] = true;for(i = 0; i < N; i++){if(visy[i]) continue;int tmp = lx[t]+ly[i]-g[t][i];if(tmp == 0){visy[i] = true;if(pre[i] == -1 || dfs(pre[i])){pre[i] = t;return true;}}else if(slack[i] > tmp){slack[i] = tmp;}}return false;}int KM(){int i, j, k;for(i = 0; i < N; i++)lx[i] = -INF;memset(ly, 0, sizeof(ly));memset(pre, -1, sizeof(pre));for(i = 0; i < N; i++)for(j = 0; j < N; j++)if(lx[i] < g[i][j])lx[i] = g[i][j];for(i = 0; i < N; i++){for(j = 0; j < N; j++) slack[j] = INF;while(1){memset(visx, false, sizeof(visx));memset(visy, false, sizeof(visy));if(dfs(i)) break;int d = INF;for(j = 0; j < N; j++)if(!visy[j] &&d > slack[j])d = slack[j];for(j = 0; j < N; j++){if(visx[j]) lx[j] -= d;if(visy[j]) ly[j] += d;else slack[j] -= d;}}}int ans = 0;for(i = 0; i < N; i++){if(pre[i] != -1)ans -= g[pre[i]][i];}return ans;}int main(){int h,v,mf,mm;// freopen("1.txt","r",stdin);scanf("%d%d",&h,&v);while(h!=0||v!=0){mm=mf=0;for(int i=0;i<h;i++)for(int j=0;j<v;j++){char c;scanf("%c",&c);while(c!='.'&&c!='H'&&c!='m')scanf("%c",&c);if(c=='H'){ff[mf][0]=i;ff[mf][1]=j;mf++;}if(c=='m'){man[mm][0]=i;man[mm][1]=j;mm++;}}N=mm;for(int i=0;i<N;i++)for(int j=0;j<N;j++)g[i][j]=-(abs(man[i][0]-ff[j][0])+abs(man[i][1]-ff[j][1]));printf("%d\n",KM());scanf("%d%d",&h,&v);}}POJ 2446 Chessboard算法：很囧的题，本来打算用搜索过的，发现深搜肯定超时，试了一下，果然超时。
c acm试题及答案ACM（Association for Computing Machinery）是计算机科学领域的国际性学术组织，旨在推动计算机科学的发展与研究。
ACM竞赛是ACM组织举办的一项计算机算法编程竞赛，每年都有数以千计的计算机专业学生参加。
这篇文章将介绍一道ACM试题，并提供解答。
题目描述：给定一个整数数组nums，其中所有元素都是非负整数，现在要求你计算nums中连续子数组的最大和，并输出该最大和。
输入：第一行输入一个整数n，表示数组长度（1 <= n <= 10^5）。
第二行输入n个整数，表示数组nums的元素（元素范围为0 <= nums[i] <= 100）。
输出：输出一个整数，表示nums中连续子数组的最大和。
示例：输入：51 2 3 4 5输出：15解释：最大和子数组为[1, 2, 3, 4, 5]，和为15。
解答：首先，我们可以使用一个变量maxSum来记录当前得到的最大和，初始化为0。
同时，我们还使用一个变量sum来记录当前连续子数组的和，初始化为0。
接下来，我们对数组nums进行遍历。
对于每一个元素nums[i]，我们将其加到sum中，并判断sum是否大于0。
如果sum大于0，说明当前连续子数组的和对后面的结果是有正向贡献的，我们可以继续累加后面的元素。
如果sum小于等于0，说明当前连续子数组的和对后面的结果没有正向贡献，我们可以将sum重新置为0，重新开始计算连续子数组的和。
在遍历过程中，我们不断更新maxSum的值，保证其为当前得到的最大和。
最终，遍历结束后的maxSum即为所求的最大和。
下面是具体的实现代码：```cpp#include <iostream>#include <vector>#include <algorithm>using namespace std;int maxSubArray(vector<int>& nums) { int maxSum = 0;int sum = 0;for(int i = 0; i < nums.size(); i++) { sum += nums[i];if(sum > maxSum) {maxSum = sum;}if(sum <= 0) {sum = 0;}}return maxSum;}int main() {int n;cin >> n;vector<int> nums(n);for(int i = 0; i < n; i++) {cin >> nums[i];}int result = maxSubArray(nums);cout << result << endl;return 0;}```以上就是解答c acm试题并提供相应代码的文章。
acm大赛试题及答案ACM大赛试题及答案1. 题目一：字符串反转问题描述：编写一个程序，输入一个字符串，输出其反转后的字符串。
输入格式：输入包含一个字符串，字符串长度不超过100。
输出格式：输出反转后的字符串。
示例：输入：hello输出：olleh答案：```pythondef reverse_string(s):return s[::-1]input_string = input().strip()print(reverse_string(input_string))```2. 题目二：计算阶乘问题描述：编写一个程序，输入一个非负整数n，输出n的阶乘。
输入格式：输入包含一个非负整数n，n不超过20。
输出格式：输出n的阶乘。
示例：输入：5输出：120答案：```pythondef factorial(n):if n == 0:return 1else:return n * factorial(n - 1)n = int(input())print(factorial(n))```3. 题目三：寻找最大数问题描述：给定一个包含n个整数的数组，找出数组中的最大数。
输入格式：输入包含一个整数n，表示数组的大小，随后是n个整数。
输出格式：输出数组中的最大数。
示例：输入：5 1 2 3 4 5输出：5答案：```pythonn = int(input())numbers = list(map(int, input().split()))max_number = max(numbers)print(max_number)```4. 题目四：判断闰年问题描述：编写一个程序，输入一个年份，判断该年份是否为闰年。
输入格式：输入包含一个整数，表示年份。
输出格式：如果输入的年份是闰年，则输出"Yes"，否则输出"No"。
示例：输入：2000输出：Yes答案：```pythonyear = int(input())if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):print("Yes")else:print("No")```5. 题目五：斐波那契数列问题描述：编写一个程序，输入一个非负整数n，输出斐波那契数列的第n项。
acm编程练习题ACM（即：美国计算机协会）编程练习题是指ACM国际大学生程序设计竞赛中的一些编程题目，旨在考察参赛选手在算法和数据结构等方面的能力。
这些题目常常要求选手设计和实现一个算法，在规定的时间和空间限制下解决实际问题。
ACM编程练习题具有一定的难度和挑战性，它的解题过程有时需要选手在理论基础上进行创新思维和灵活运用。
相比于传统的笔试或面试形式，ACM编程练习题更加贴近实际应用场景，能够真实地展现参赛选手的编程能力和逻辑思维能力。
为了更好地完成ACM编程练习题，选手需要熟练掌握常用的数据结构和算法，比如数组、链表、栈、队列、树、图等。
此外，对于一些经典的算法，如贪心算法、动态规划、分治法等，也有必要进行深入学习和理解。
在真实的竞赛环境中，选手还需要熟悉特定的编程语言和开发环境，比如C++、Java或Python等。
解决ACM编程练习题有着多种方法和思路。
选手需要熟悉各种问题的特点，根据问题所给条件进行合理的算法设计。
对于一些复杂的问题，可以利用数学方法进行简化和转化，从而找到更高效的解决方案。
在编程实现的过程中，要注重代码的可读性和可维护性，合理地使用注释和命名，避免代码冗余和错误。
ACM编程练习题的解题过程中，选手不仅需要具备扎实的编程基础和算法知识，还需要具备压力下的良好心态和团队合作精神。
在竞赛中，选手可能面临时间紧迫、出题者的陷阱、复杂场景等挑战，因此，选手们需要保持冷静、灵活应对，不断提升自己的解题能力和竞赛技巧。
总之，ACM编程练习题是一种非常有挑战性的编程竞赛形式，对选手的编程能力、算法思维和团队协作能力都提出了较高的要求。
通过积极参与练习和实战，选手们可以不断提升自己，在ACM竞赛中取得更好的成绩，并在实际工作中具备更强的编程能力。
（字数：413）。
ACM竞赛试题集锦（2020年九⽉整理）.doc取⽯⼦游戏Time Limit:1S Memory Limit:1000KTotal Submit:505 Accepted:90Description有两堆⽯⼦，数量任意，可以不同。
游戏开始由两个⼈轮流取⽯⼦。
游戏规定，每次有两种不同的取法，⼀是可以在任意的⼀堆中取⾛任意多的⽯⼦；⼆是可以在两堆中同时取⾛相同数量的⽯⼦。
最后把⽯⼦全部取完者为胜者。
现在给出初始的两堆⽯⼦的数⽬，如果轮到你先取，假设双⽅都采取最好的策略，问最后你是胜者还是败者。
Input输⼊包含若⼲⾏，表⽰若⼲种⽯⼦的初始情况，其中每⼀⾏包含两个⾮负整数a 和b，表⽰两堆⽯⼦的数⽬，a和b都不⼤于1,000,000,000。
Output输出对应也有若⼲⾏，每⾏包含⼀个数字1或0，如果最后你是胜者，则为1，反之，则为0。
Sample Input2 18 44 7Sample Output1跳蚤Time Limit:1S Memory Limit:1000KTotal Submit:198 Accepted:44DescriptionZ城市居住着很多只跳蚤。
在Z城市周六⽣活频道有⼀个娱乐节⽬。
⼀只跳蚤将被请上⼀个⾼空钢丝的正中央。
钢丝很长，可以看作是⽆限长。
节⽬主持⼈会给该跳蚤发⼀张卡⽚。
卡⽚上写有N+1个⾃然数。
其中最后⼀个是M，⽽前N个数都不超过M，卡⽚上允许有相同的数字。
跳蚤每次可以从卡⽚上任意选择⼀个⾃然数S，然后向左，或向右跳S个单位长度。
⽽他最终的任务是跳到距离他左边⼀个单位长度的地⽅，并捡起位于那⾥的礼物。
⽐如当N=2，M=18时，持有卡⽚(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。
⽽持有卡⽚(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边⼀个单位长度的地⽅。
acm数学竞赛试题及答案# 题目一：数列问题问题描述：给定一个数列 \( a_1, a_2, a_3, \ldots, a_n \)，数列中每个元素都是正整数，且满足 \( a_i = a_{i-1} + a_{i-2} \) 对于所有\( i \geq 3 \)。
如果 \( a_1 = 1 \) 且 \( a_2 = 1 \)，请找出数列的第 \( n \) 项。
解答：根据题意，这是一个斐波那契数列。
第 \( n \) 项的值可以通过递归关系计算得出。
对于 \( n \) 的值，可以使用以下递归公式：\[ a_n = a_{n-1} + a_{n-2} \]其中，\( a_1 = 1 \) 和 \( a_2 = 1 \)。
因此，数列的前几项为 1, 1, 2, 3, 5, 8, 13, 21, ...。
对于任意的 \( n \)，可以通过递归或动态规划方法计算出 \( a_n \)。
# 题目二：组合问题问题描述：从 \( n \) 个不同的元素中选择 \( k \) 个元素的所有可能组合的个数是多少？解答：这个问题可以通过组合数学中的二项式系数来解决。
从 \( n \) 个不同元素中选择 \( k \) 个元素的组合数 \( C(n, k) \) 可以用以下公式计算：\[ C(n, k) = \frac{n!}{k!(n-k)!} \]其中，\( n! \) 表示 \( n \) 的阶乘。
# 题目三：几何问题问题描述：在一个直角坐标系中，给定三个点 \( A(x_1, y_1) \)，\( B(x_2, y_2) \) 和 \( C(x_3, y_3) \)。
如果 \( \overrightarrow{AB} \) 和 \( \overrightarrow{AC} \) 是垂直的，求证 \( A \) 是直角三角形 \( ABC \) 的直角顶点。
解答：如果 \( \overrightarrow{AB} \) 和 \( \overrightarrow{AC} \) 垂直，那么它们的数量积（点积）应该为零。
poj 1061 青蛙的约会这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。
内容如下：对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。
符号说明：mod表示：取模运算ax≡b(mod m)表示：(ax - b) mod m = 0，即同余gcd(a,b)表示：a和b的最大公约数求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。
而ax≡b(mod n)的解可以由x，y来堆砌。
具体做法如下：第一个问题：求解gcd(a,b)定理一：gcd(a,b) = gcd(b,a mod b)欧几里德算法int Euclid(int a,int b){if(b == 0)return a;elsereturn Euclid(b,mod(a,b));}附：取模运算int mod(int a,int b){if(a >= 0)return a % b;elsereturn a % b + b;}第二个问题：求解ax + by = gcd(a,b)定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y'= b * x' + (a - a / b * b) * y'= a * y' + b * (x' - a / b * y')= a * x + b * y则：x = y'y = x' - a / b * y'以上内容转自/redcastle/blog/item/934b232dbc40d336349bf7e4.html由这个可以得出扩展的欧几里德算法：int exGcd(int a, int b, int &x, int &y) {if(b == 0){x = 1;y = 0;return a;}int r = exGcd(b, a % b, x, y);int t = x;x = y;y = t - a / b * y;return r;}代码：#include<iostream>#include<cstdlib>#include<cstring>#include<cmath>using namespace std;__int64 mm,nn,xx,yy,l;__int64 c,d,x,y;__int64 modd(__int64 a, __int64 b){if(a>=0)return a%b;elsereturn a%b+b;}__int64 exGcd(__int64 a, __int64 b) {if(b==0){x=1;y=0;return a;}__int64 r=exGcd(b, a%b);__int64 t=x;x=y;y=t-a/b*y;return r;}int main(){scanf("%I64d %I64d %I64d %I64d %I64d",&xx,&yy,&mm,&nn,&l);if(mm>nn) //分情况{d=exGcd(mm-nn,l);c=yy-xx;}else{d=exGcd(nn-mm,l);c=xx-yy;}if(c%d != 0){printf("Impossible\n");return 0;}l=l/d;x=modd(x*c/d,l); ///取模函数要注意printf("%I64d\n",x);system("pause");return 0;}POJ 1142 SmithNumber题意：寻找最接近而且大于给定的数字的SmithNumber什么是SmithNumber？用sum(int)表示一个int的各位的和，那一个数i如果是SmithNumber,则sum（i） =sigma( sum(Pj )),Pj表示i的第j个质因数。
例如4937775= 3*5*5*65837，4+9+3+7+7+7+5 = 42，3+5+5+（6+5+8+3+7） = 42，所以4937775是SmithNumber。
思路：要寻找大于给定数字且最接近给定数字的SmithNumber，只要将给定数字不断的加1，判断它是否是SmithNumber就行了，如果是SmithNumber就立即输出。
但是如何判断是否是SmithNumber呢？首先就是要对数字进行质因数分解。
质因数分解要保证因子都是质数。
这里先介绍一个如何判断一个数int是否是质数呢，如果对于这个数，i = 2.....sqrt(int)都不是它的约数，那int就是一个质数。
所以我们可以将i初始化为2，然后不断递增i，看i是否是int的一个约数，如果是的话那i就是int的一个质因数（因为这个数是从2开始第一个可以整除int的数，它不可能是一个可以分解的合数，否则，它的约数在它之前就整除int），然后将int除以该质因数，重置i为2，重新对int判断它是否是质数。
这样最后剩下的int一定是一个质数，从而对int进行了质因数分解然后就很简单的将数字各质因数的各位加起来，看和是否等于该数字的各位和，如果相等那它可能就是SmithNumber，为什么说只是可能呢，因为这个数可能是质数，但是质数不是SmithNumber。
#include <stdio.h>#include <math.h>int Sum( int number ){int sum = 0;while( number != 0 ){sum += number % 10;number /= 10;}return sum;}bool SmithNumber( int number ){int i = 2;int temp = number;int sumOfNumber = Sum( number );int sum = 0;while( i <= (int)sqrt( (double)number ) ){if ( number % i ==0 ){sum += Sum( i );number /= i;i = 2;}else{++i;}//以上的代码做了无谓的计算，可用下面的代码，更新于20090904 //while( number % i == 0 )//{// sum += sum(i);// number /= i;//}// ++i;}sum += Sum( number );if ( sum == sumOfNumber && number != temp ){return true;}else{return false;}}int main(){while( true ){int num;scanf("%d",&num );if ( num == 0 ){break;while( true ){if ( SmithNumber(++num)){printf("%d\n", num);break;}}}return 0;}ACM——POJ 2262（Goldbach's Conjecture）题目地址：/JudgeOnline/problem?id=2262题目思路：对于任何一个偶数 n，从 x = 1 和 y = n - 1 开始，看 x、y 是否是质数，不是则 x += 2, y += 2这题需要开很大的内存，我 RE n 次，居然是因为数组开太小了，我这题耗时不是很理想，但我的耗内存在我看到的中是最小的，所以看来 OJ 上的题只要能开内存的就尽量开。
估计我这题用栈耗时了。
#include <iostream>#include <stdio.h>#include <math.h>#include <stack>#include <memory.h>#include <string.h>using namespace std;// 判断是否为质数的函数int IsPrime ( int x ){int i;if( x < 2 )return 0;for( i = 2; i <= (int) ( sqrt( (double)x + 0.5 ) ); i++ )if( x % i == 0)return 0;return 1;int main(){// 输入数，输入数 / 2 向上延伸，输入数 / 2 向下延伸，输入数 / 2int m_Input, m_Num_Max, m_Num_Min, m_InputToTwo;// 总体输出char m_Output[ 1000000 ];memset( m_Output, 0, 1000000 );// 标识 m_Output 的 Posint m_Output_Pos = 0;// 是否找到标识bool b_Find;// 栈stack<int> m_Stack;// 临时数int m_Value_Top;// 循环输入while ( scanf( "%d", &m_Input ) && ( m_Input != 0 ) ){b_Find = true;// m_Input 肯定是一个偶数m_InputToTwo = m_Input / 2;// 置值m_Num_Max = m_Input - 1;m_Num_Min = 1;// 寻找，直至都为素数或者找不到为止while ( ( !IsPrime( m_Num_Max ) ) || ( !IsPrime( m_Num_Min ) ) ){// 否则，前进 & 后退 2 格m_Num_Max -= 2;m_Num_Min += 2;// 如果发生如下情况，则输出 "Goldbach's conjecture is wrong."if ( ( m_Num_Max < m_InputToTwo ) || ( m_Num_Min > m_InputToTwo ) ){char* m_TempChar = "Goldbach's conjecture is wrong.\n"; strcat( m_Output, m_TempChar );b_Find = false;m_Output_Pos += strlen( m_TempChar );break;}}// 如果找到了if ( b_Find ){// 将 m_Input 转换为字符串存入 m_Outputwhile ( m_Input != 0 ){m_Value_Top = m_Input % 10;m_Stack.push( m_Value_Top );m_Input /= 10;}while ( !m_Stack.empty() ){m_Value_Top = m_Stack.top();m_Output[ m_Output_Pos++ ] = m_Value_Top + 48;m_Stack.pop();}// 加入 =m_Output[ m_Output_Pos++ ] = ' ';m_Output[ m_Output_Pos++ ] = '=';m_Output[ m_Output_Pos++ ] = ' ';// 将 m_Num_Min 转换为字符串存入 m_Outputwhile ( m_Num_Min != 0 ){m_Value_Top = m_Num_Min % 10;m_Stack.push( m_Value_Top );m_Num_Min /= 10;}while ( !m_Stack.empty() ){m_Value_Top = m_Stack.top();m_Output[ m_Output_Pos++ ] = m_Value_Top + 48;m_Stack.pop();}// 加入 +m_Output[ m_Output_Pos++ ] = ' ';m_Output[ m_Output_Pos++ ] = '+';m_Output[ m_Output_Pos++ ] = ' ';// 将 m_Num_Max 转换为字符串存入 m_Outputwhile ( m_Num_Max != 0 ){m_Value_Top = m_Num_Max % 10;m_Stack.push( m_Value_Top );m_Num_Max /= 10;}while ( !m_Stack.empty() ){m_Value_Top = m_Stack.top();m_Output[ m_Output_Pos++ ] = m_Value_Top + 48;m_Stack.pop();}// 加入 \nm_Output[ m_Output_Pos++ ] = '\n';}}// 输出printf( "%s", m_Output );system( "pause" );return 0;}POJ 2407 Relatives这题从题意可以看出就是求比从1~n - 1从有几个数和n没有公共因子，通常的算法很简单就能够想到，我开始也是按通常的做法写了一个，觉得可能会TLE, 果不其然，后来上网查了一下，知道了欧拉函数，这个就是求比n小的数中与n互质（也就是没有公共因子）的算法，看来还是那些经典的算法效率比较高，比纯用暴力试探高多了...欧拉函数描述如下：利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。
