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