首页 > 代码库 > HDU1099---数学 | 思维
HDU1099---数学 | 思维
hdu 1099 Lottery
题意:1~n编号的彩票,要买全,等概率条件下平均要买几张。
已经买了m张时,买中剩下的概率为1-m/n,则要买的张数为1/(1-m/n)
n=2,s=1+1/(1-1/2);n=3,s=1+1/(1-1/3)+1/(1-2/3)
s=1+1/(1-1/n)+1/(1-2/n)+1/(1-3/n)+……+1/(1-(n-1)/n)=n/n+n/(n-1)+n/(n-2)+……+n/1=sum(n/i),i=1~n
b/a+d/c=(bc+ad)/(ac)
然后递推着通分,化简;输出。
///实现 sum(n/i) (i=1~n) #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cmath> #include<string> #include<algorithm> using namespace std; #define LL long long LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } struct fen{ LL a,b; }; fen& add(struct fen&a,struct fen&b) { a.a=a.a*b.b+a.b*b.a; a.b=a.b*b.b; LL t=gcd(a.a,a.b); a.a/=t; a.b/=t; return a; } int ditNum(LL a) { int cnt=0; while(a) { cnt++; a/=10; } return cnt; } int main() { int n; LL fenz=0,fenm=0; struct fen f,f1; while(~scanf("%d",&n)) { f.a=n;f.b=1; for(int i=2;i<=n;i++) { f1.a=n;f1.b=i; f=add(f,f1); } if(f.a%f.b==0) { cout<<f.a/f.b<<endl; } else { LL t=f.a/f.b; int a=ditNum(t),b=ditNum(f.b); a++; int x=a; while(a--) cout<<" "; cout<<f.a-t*f.b<<endl; cout<<t<<" "; while(b--) cout<<"-"; cout<<endl; while(x--) cout<<" "; cout<<f.b<<endl; } } }
HDU1099---数学 | 思维
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。