[SHOI2002]百事世界杯之旅

洛咕

双倍经验

题意:每张彩票上有一个漂亮图案，图案一共n种，如果你集齐了这n种图案就可以兑换大奖.请问在理想（平均）情况下，你买多少张彩票才能获得大奖？

分析:洛咕日报上看到的题.上面讲了一点题解,反正我没看懂.总之结论就是\((\sum_{i=1}^n\frac{1}{i})*n.\)

本题可谓是集齐了打代码时的所有神坑细节,什么爆\(int\)啊,奇怪的输出格式啊,分数要各种约分啊....本来这种数学期望,推结论就够难了,还要为难输出.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline ll gcd(ll a,ll b){
    if(!b)return a;
    return gcd(b,a%b);
}
int main(){
    int n=read();
    if(n==1){puts("1");return 0;}
    if(n==2){puts("3");return 0;}//特判前面两个
    ll lcm=2;
    for(int i=3;i<=n;++i)lcm=(lcm*i)/gcd(lcm,i);//找到1到n 的最小公倍数
    ll tot=0;
    for(int i=1;i<=n;++i)tot+=lcm/i;//算出分子之和
    ll fm=lcm/n;//先把结论中的n给乘上,也就是让分母除n
    ll zs=tot/fm;//计算整数部分
    ll fz=tot%fm;//除不尽就算出分子部分
    if(!fz)printf("%lld\n",zs);//没分子,即恰好为整数
    else{
        ll GCD=gcd(fz,fm);fz/=GCD;fm/=GCD;//分子分母约分
        ll cnt1=zs,sum1=0;
        while(cnt1){++sum1;cnt1/=10;}
        ll cnt2=fm,sum2=0;
        while(cnt2){++sum2;cnt2/=10;}//分别计算位数,为了打空格和减号
        for(int i=1;i<=sum1;++i)printf(" ");
        printf("%lld\n%lld",fz,zs);
        for(int i=1;i<=sum2;++i)printf("-");
        printf("\n");
        for(int i=1;i<=sum1;++i)printf(" ");
        printf("%lld\n",fm);
    }

    return 0;
}

多组数据的代码(输出格式有变化)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline ll gcd(ll a,ll b){
    if(!b)return a;
    return gcd(b,a%b);
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        if(n==1){puts("1");continue;}
        if(n==2){puts("3");continue;}
        ll lcm=2;
        for(int i=3;i<=n;++i)lcm=(lcm*i)/gcd(lcm,i);
        ll tot=0;
        for(int i=1;i<=n;++i)tot+=lcm/i;
        ll fm=lcm/n;
        ll zs=tot/fm;
        ll fz=tot%fm;
        if(!fz)printf("%lld\n",zs);
        else{
            ll GCD=gcd(fz,fm);fz/=GCD;fm/=GCD;
            ll cnt1=zs,sum1=0;
            while(cnt1){++sum1;cnt1/=10;}
            ll cnt2=fm,sum2=0;
            while(cnt2){++sum2;cnt2/=10;}
            for(int i=1;i<=sum1+1;++i)printf(" ");
            printf("%lld\n%lld ",fz,zs);
            for(int i=1;i<=sum2;++i)printf("-");
            printf("\n");
            for(int i=1;i<=sum1+1;++i)printf(" ");
            printf("%lld\n",fm);
        }
    }
    return 0;
}