蓝杯三十九
算法提高 欧拉函数
时间限制：1.0s 内存限制：512.0MB
提交此题
说明
2016.4.5 已更新试题，请重新提交自己的程序。
问题描述
给定一个大于1，不超过2000000的正整数n，输出欧拉函数，phi(n)的值。
如果你并不了解欧拉函数，那么请参阅提示。
输入格式
在给定的输入文件中进行读入：
一行一个正整数n。
输出格式
将输出信息输出到指定的文件中:
一行一个整数表示phi(n)。
样例输入
17
样例输出
16
提示
欧拉函数phi(n)是数论中非常重要的一个函数，其表示1到n-1之间，与n互质的数的个数。显然的，我们可以通过定义直接计算phi(n)。
当然，phi(n)还有这么一种计算方法。
首先我们对n进行质因数分解，不妨设n=p1^a1 * p2^a2 * ... * pk^ak （这里a^b表示a的b次幂，p1到pk为k个互不相同的质数，a1到ak均为正整数），那么
phi(n)=n(1-(1/p1))(1-(1/p2))....(1-(1/pk))
稍稍化简一下就是
phi(n)=n(p1-1)(p2-1)...(pk-1)/(p1*p2*...*pk)
计算的时候小心中间计算结果超过int类型上界，可通过调整公式各项的计算顺序避免(比如先做除法)!
#include<cstdio>
int euler(int n){ //返回euler(n)
int res=n,a=n;
for(int i=2;i*i<=a;i++){//从小到大尝试n的质因数
if(a%i==0){//如果i是n的质因数
res=res/i*(i-1);//提了一个1/i出来，先进行除法是为了防止中间数据的溢出
while(a%i==0) a/=i;//欧拉函数只记算一种质因数
}
}
if(a>1) res=res/a*(a-1);//如果最后还剩因子
return res;
}
int main(){
int x;
scanf("%d",&x);
printf("%d",euler(x));
return 0;
}
思路分析：
①定义变量：一个整数；
②输入一个整数；
③调用函数：
（1）定义变量；
（2）for语句从小到大尝试n的质因数 ；
（3）if语句判断i是否是n的质因数，如果是，则 提了一个1/i出来，先进行除法是为了防止中间数据的溢出 ；
（4）while语句循环：欧拉函数只记算一种质因数 ；
（5）if语句判断是否最后还剩因子 ；
（6）返回值；
④输出欧拉函数。
算法提高 前10名
时间限制：1.0s 内存限制：256.0MB
提交此题
问题描述
数据很多，但我们经常只取前几名，比如奥运只取前3名。现在我们有n个数据，请按从大到小的顺序，输出前10个名数据。
输入格式
两行。
第一行一个整数n，表示要对多少个数据
第二行有n个整数，中间用空格分隔。表示n个数据。
输出格式
一行，按从大到小排列的前10个数据，每个数据之间用一个空格隔开。
样例输入
26
54 27 87 16 63 40 40 22 61 6 57 70 0 42 11 50 13 5 56 7 8 86 56 91 68 59
样例输出
91 87 86 70 68 63 61 59 57 56
数据规模和约定
10<=n<=200,各个整数不超出整型范围
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
int a[200],i,j,t;
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++){
for(j=0;j<n-1;j++){
if(a[j]<a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
}
思路分析：
① 定义变量：一个整数，一组数据（一维数组），循环次数；
②输入一个整数；
③for语句循环输入数组数据；
④for语句双重循环，if语句判断从大到小排序；
⑤for语句输出前十数据。
