NYOJ 576 集齐卡片赢大奖（一）

 1 #include<stdio.h>
 2 #include<math.h>
 3 int main()
 4 {
 5     double ans;
 6     int n;
 7     while(~scanf("%d",&n)){
 8         if(n<10000){
 9             ans=0.0;
10             for(int i=1;i<=n;i++)
11                 ans+=1.0*n/i;
12             printf("%lld\n",(long long)(ans+0.5));
13         }else{
14             printf("%lld\n",(long long)(n*(log(n+1)+0.5772156649)));
15         }
16     }
17     return 0;
18 }

收集一种卡片的概率为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.5772156649) 其中常数为欧拉常数

最后注意前面当n不是很大的时候不能用公式!

本题WA无数次，最后经南工ACM群中大神指点和聪神的测试数据才得以AC!