nyoj576 集齐卡片赢大奖(一)

时间:2022-03-09 12:04:11

集齐卡片赢大奖(一)

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
 
描述

小时候你一定曾经为收集一套三国人物的卡片而买过不少零食吧?这些小吃的袋子里一般都会有一张卡片,如果你能收集一整套的话,你就可以去兑奖了,结果你买了不少零食却怎么也集不齐一套……

为了简单起见,我们假设每包零食都会有且只有一张卡片,而每种卡片的数量都相等并且都有无穷多张,那么我们现在就来计算一下,平均来说你收集一套有n种的卡片需要买多少包这样的零食呢?

 
输入
多组测试数据,每行一个整数n(1<1<10^9),以文件结束。
输出
每个结果占一行,四舍五入为整数。
样例输入
1
5
999999999
样例输出
1
11
21300481480 讲解:

收集一种卡片的概率为1,然后再买一袋即可收集2种的概率(n-1)/n,

所以期望为n/(n-1)依次类推,得到所有的期望为:

f[n_] := Sum[n/k, {k, 1, n}]

上式可以优化,利用高数学的基数,Ln(n)=(1+1/2+1/3+....+1/n),可以精简为

n*(Ln(n)+0.) 其中常数为欧拉常数

代码一:

 #include<stdio.h>
#include<math.h>
int main()
{
double ans;
int n;
while(~scanf("%d",&n))
{
if(n<)
{
ans=0.0;
for(int i=;i<=n;i++)
ans+=1.0*n/i;
printf("%lld\n",(long long)(ans+0.5));
}
else{
printf("%lld\n",(long long)(n*(log(n+)+0.5772156649)));
}
}
return ;
}

代码二:

 #include<stdio.h>
#include<math.h>
#define Y 0.57721566490153286060651209
int main()
{
double n;
while(~scanf("%lf",&n))
printf("%.0lf\n",(log(n)+Y)*n+0.49999);
}