[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;
}