当前位置: 58彩票app下载 > 编程技术 > 正文

阶乘之和,蓝杯三十九

时间:2019-09-21 18:39来源:编程技术
题目:输入n,计算S = 1! + 2! +3! +...+n!的末6位。n ≤ 10^6,n!表示前n个正整数之积。 算法提升 欧拉函数 样例输入: 时间限制:1.0s 内存限制:512.0MB 10 付出此题 样例输出: 说明 37913 20

题目:输入n,计算S = 1! + 2! +3! +...+ n!的末6位。n ≤ 10^6,n!表示前n个正整数之积。

算法提升 欧拉函数

样例输入:

时间限制:1.0s 内存限制:512.0MB

10

付出此题

样例输出:

说明

37913

2015.4.5 已更新试题,请重新提交本人的次第。

引进累加变量S之后,核心算法独有“for(int i = 1; i <= n; i++) S += i!”。但是,C语言并未阶乘运算符,所以那句话只是伪代码,并非真正的代码。事实上,还亟需种种一回巡回还总计i!,即“for(int j = 1;j <=i;j++) factorial = factorial * j;”。代码如下:

标题汇报

#include<stdio.h>#include<time.h>int main(){  const int MOD = 1000000;  int num,sum = 0;  scanf("%d",&num);  for(int i = 1 ; i <= num ; i++){    int factorial = 1;    for(int j = 1 ; j <= i;j++){      factorial = factorial * j % MOD;//取模防止溢出    }    sum = (sum + factorial) % MOD;  }    printf("%dn",sum);  printf("Time used = %.2fn",(double)clock() / CLOCKS_PER_SEC);//计时函数  return 0;      }

给定贰个不仅仅1,不超越两千000的正整数n,输出欧拉函数,phi的值。

唤醒:在循环体最早处定义的变量,每趟试行循环体时会重新表明并开端化。

万一你并不打听欧拉函数,那么请参阅提醒。

唤醒:要计算只满含加法、减法和乘法的板寸表达式除以正整数n的余数,可以在每步总计之后对n取余,结果不改变。

输入格式

在加以的输入文件中开展读入:

一行一个正整数n。

输出格式

将出口音信输出到钦定的文书中:

一行三个卡尺头表示phi。

样例输入

17

样例输出

16

提示

欧拉函数phi是数论中拾壹分首要的叁个函数,其象征1到n-1之间,与n互质的数的个数。分明的,大家得以由此定义直接总计phi。

本来,phi还应该有那样一种总括方法。

率先大家对n进行质因数分解,无妨设n=p1^a1 * p2^a2 * ... * pk^ak (这里a^b表示a的b次幂,p1到pk为k个互不一样样的质数,a1到ak均为正整数),那么

phi=n....

稍稍化简一下正是

phi=n.../(p1*p2*...*pk)

总结的时候当心中间总结结果超越int类型上界,可经过调节公式每一种的乘除顺序幸免!

#include<cstdio>

int euler{ //返回euler

int res=n,a=n;

for(int i=2;i*i<=a;i++){//从小到大尝试n的质因数

if{//即使i是n的质因数

res=res/i*;//提了三个1/i出来,先进行除法是为着防御中间数据的溢出

while a/=i;//欧拉函数只记算一种质因数

}

}

if res=res/a*;//假若最终还剩因子

return res;

}

int main(){

int x;

scanf("%d",&x);

printf("%d",euler;

return 0;

}

思路剖析:

①定义变量:贰个整数;

②输入八个整数;

③调用函数:

概念变量;

for语句从小到大尝试n的质因数 ;

if语句判定i是不是是n的质因数,假设是,则 提了三个1/i出去,先进行除法是为着幸免中间数据的溢出 ;

while语句循环:欧拉函数只记算一种质因数 ;

if语句判定是否最后还剩因子 ;

返回值;

④输出欧拉函数。

算法提升 前10名

时限:1.0s 内部存款和储蓄器限制:256.0MB

交给此题

标题陈诉

数据非常多,但大家日常只取前几名,譬如奥林匹克运动只取前3名。今后我们有n个数据,请按从大到小的种种,输出前13个名数据。

输入格式

两行。

先是行贰个卡尺头n,表示要对有个别个数据

第二行有n个整数,中间用空格分隔。表示n个数据。

出口格式

一行,按从大到小排列的前13个数据,每一个数据里面用叁个空格隔断。

样例输入

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语句输出前十数量。

编辑:编程技术 本文来源:阶乘之和,蓝杯三十九

关键词: