百事世界杯之旅

解题思路：

//示例代码 C++

#include <cstdio>
#include <cmath>

long long n;

long long gcd(long long a,long long b)
//求最大公约数（用于约分和通分）
{
    if(!b)
    {
        return a;
    }
    return gcd(b,a%b);
}

int getlen(long long a)
//求一个数的位数（用于输出）
{
    return (int)(log(a)/log(10))+1;
}

struct frac
{
    long long z,m;

    int join(long long a,long long b)
    //构造一个分数，值为a/b
    {
        z=a;
        m=b;
        int y=gcd(z,m);
        z/=y;
        m/=y;
        //上面三步是约分
        return 0;
    }

    frac operator +=(const frac &other)
    //加法
    {
        long long pu=m*other.m/gcd(m,other.m);
        //pu是最简公分母
        z*=pu/m;
        long long otherz=other.z;
        otherz*=pu/other.m;
        m=pu;
        //上面4步是通分
        z+=otherz;
        //上面这一步是加法
        long long y=gcd(m,z);
        m/=y;
        z/=y;
        //上面三步是约分
        return *this;
    }

    int print()
    {
        long long pzh=z/m;
        long long pz=z-(z/m)*m;
        //pzh是带分数形式的整数部分，pz是带分数形式的分子
        if(pz)
        //如果有分子的话，输出分子
        {
            for(int i=1; i<=getlen(pzh); i++)
            {
                putchar(' ');
            }
            printf("%lld\n",pz);
        }
        printf("%lld",pzh);
        //输出整数部分
        if(pz)
        //如果有分数部分的话，输出分数线和分母
        {
            for(int i=1; i<=getlen(m); i++)
            {
                putchar('-');
            }
            putchar('\n');
            for(int i=1; i<=getlen(pzh); i++)
            {
                putchar(' ');
            }
            printf("%lld",m);
        }
        return 0;
    }
};

frac ans;

int main()
{
    scanf("%lld",&n);
    ans.join(0,1);
    //求sum(n/i)
    for(long long i=1; i<=n; i++)
    {
        frac x;
        x.join(n,i);
        ans+=x;
    }
    ans.print();
    putchar('\n');
    return 0;
}

 

 

 

参考答案：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long a, b, p;
long long gcd(long long a, long long b)      //求最大公约数,参与分数计算，使用long long型函数
{                                            //此GCD函数建议直接背下来，所有输出分数的题全部都要用到
  if (b == 0) return a;
  return gcd(b, a%b);
}

int main() {                                //题意为：从n种数中选出n个不同数的期望次数。
  int n, i; cin >> n; a = 1; b = 1;       //所以第一个球星抽到的概率是1，第n个是1/n。那么我们要从k个到k+1个球星的概率为（n-k）/n,所以期望为n/（n-k）。
  for (i = 2; i <= n; i++) {              //答案即为ANS=n(1/1+1/2+1/3+....1/n)
    a = a*i + b; b *= i;
    p = a; a /= gcd(a, b); b /= gcd(p, b);//计算 
  }
  a *= n;
  if (a%b == 0)cout << a / b;
  else {
    cout << a / b; a -= b*(a / b);
    cout << '(' << a / gcd(a, b) << '/' << b / gcd(a, b) << ')';//输出 
  }
  system("pause");
  return 0;
}