刷水题ing
做的第一道迭代加深题（也是最经典的一道）
（这么水应该就不要讲了吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// <1308.cpp> - 03/11/16 00:02:32 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } int D; lol ans[100],ANS[100]; void tf(lol &a,lol &b){ lol k=__gcd(a,b); a/=k;b/=k; } bool src(lol a,lol b,int d){ if(d++==D){ if(a)return 0; if(!ANS[D]||ans[D]<ANS[D])for(int i=1;i<=D;i++)ANS[i]=ans[i]; return 1; } bool r=0; ans[d]=max(ans[d-1]+1,(b-1)/a+1); for(;;ans[d]++){ if((D-d+1)*b<a*ans[d])break; lol na=a*ans[d]-b,nb=b*ans[d]; tf(na,nb); r|=src(na,nb,d); } return r; } int main(){ lol a=getint(),b=getint(); tf(a,b); for(ans[0]=0;b>a*ans[0]+a;ans[0]++); for(D=1;;D++) if(src(a,b,0)){ for(int i=1;i<=D;i++)printf("%lld ",ANS[i]); return 0; } } |
说点什么