杭电ACM3637 求算法

杭电ACM3637 求算法
看起来是水题~但我写了2天的结果就是过了样例 提交WA 我是直接暴力递增分母  但目测一定不行!

这道题目,题意：给出一个开区间（开区间由两个小数表示,[]内的是无限循环部分）,求一个分数,使得分数在这个区间里,这个分数的分子分母之和最小.
思路：
以 z1z2.c1c2[a1a2..an]
1.
开始,发现1/9=0.[1] 1/99=0.[01] 1/999=0.[001] .,于是发现了[a1a2a3a4...an]=a1a2a3a4.an/9999..9(n个),对于不循环部分c1c2直接除以100..n即可.这样,我们就把区间化成了两个分数a/b c/d.
2.
然后,我们要求x,y   使得 a/b<x/y<c/d 显然c!=0 否则无解不符题意
这个式子等价于（暂不考虑a=0 ） d/c<y/x<b/a 
如果不等式的左右两个值横跨一个整数,整数就是答案ans/1
否则 整个不等式同时减去 d/c 得 d%c/c < [y-(d/c)*x]/x   < [b-(d/c)*a]/a
这样,这个不等式的数值一直在减小,最后一定会使得 不等式的左右两个值 横跨一个整数,这个整数就是答案ans/1.类似扩展欧几里得感觉.最后,根据不等式的变换过程,再把ans/1还原回去.
（中间有点小问题,如__int64,不要超界）#include<iostream>
#include<math.h>
using namespace std;
#define eps 1e-14
char s1[20],s2[20];
__int64 gcd(__int64 a,__int64 b)
{
    if(b==0)return a;
    else return (gcd(b,a%b));
}
__int64 Lcm(__int64 a,__int64 b)
{
return a/gcd(a,b)*b;
}
int flag1,flag2;
void getFenshu(__int64 &a,__int64 &b,char *s)
{
    __int64 ls,i,sum,temp,j,lcm;
    __int64 ta,tb,bb;
    __int64 a1,b1,a2,b2;
    ls=strlen(s);
    sum=ta=tb=0;
    for(i=0;i<ls;i++)
    {
        if(s[i]=='.')
        {
            break;
        }
        sum=sum*10+(s[i]-'0');
    }
////////////////
for(j=i;j<ls;j++)
   if(s[j]>='0' && s[j]<='9')
   {flag1=sum;break;}
    if(i==ls)
    {
        a=sum;
        b=1;
        return;
    }
    b1=1;
    for(i++;i<ls;i++)
    {
        if(s[i]=='[')
            break;
        b1*=10;
        ta=ta*10+(s[i]-'0');
    }
    a1=ta;
    bb=b1;
    temp=gcd(a1,b1);
    a1/=temp;
    b1/=temp;              //a1/b1表示有限分数
    a1+=b1*sum;            //a1/b1表示有限分数+整数部分
    if(i==ls){a=a1,b=b1; return;}
    a2=0;
    b2=9;
    for(i++;i<ls;i++)
    {
        if(s[i]!=']')
            a2=a2*10+(s[i]-'0');
        else break;
        b2=b2*10+9;
    }
b2=(b2-9)/10;
temp=gcd(a2,b2);
    a2/=temp;
    b2/=temp;            //a2/b2表示无线循环分数部分
    
    b2*=bb;
    
/* temp=gcd(a1,b2)*gcd(a2,b1);
    a1=(a1*b2+a2*b1)/temp;
    b1=b1/temp*b2;
    */
lcm=Lcm(b1,b2);
a1=lcm/b1*a1+lcm/b2*a2;
b1=lcm;

    a=a1;
    b=b1;            //a1/b1表示有限分数

    return;
}
__int64 Ceil(double a)
{
    return ((__int64) a+1);    
}
__int64 Floor(double a)
{
    if(fabs(a-(__int64)a)<eps)return (__int64)a-1;
    return ((__int64)a);
}
__int64 x,y,step;
__int64 yy[1000],xx[1000],temp2;
__int64 getAns(__int64 a1,__int64 b1,__int64 a2,__int64 b2)
{
if(a1==0)
{
  
// return 1;
}
    __int64 a,b;
    a=Floor((double)a2/b2);
    b=Ceil((double)a1/b1);
    if(a>=b)
    {
   step++;
        return b;
    }
    else
    {
   step++;
   a=Ceil((double)b2/a2);
   if(a1==0)
   {
    return a;
   }
        b=Floor((double)b1/a1);
    
        
   if(step%2 && a2)
    yy[step]=b2/a2;
   else if(a2)
    xx[step]=b2/a2;
        if(b>=a)
   {
    return a;
   }
        return getAns(b2%a2,a2,b1-a1*(__int64)(b2/a2),a1);
    }
}
int main()
{
// freopen("F.in","r",stdin);
    __int64 n,i,ii,tt=0;
    __int64 temp;
    __int64 a1,b1,a2,b2;
    __int64 a,b;
int ff,ff2;
    scanf("%I64d",&n);
    getchar();
    for(ii=0;ii<n;ii++)
    {
        scanf("%s%s",&s1,&s2);
        getFenshu(a1,b1,s1);
   ff=flag1;
        getFenshu(a2,b2,s2);
   ff2=flag1;
        step=1;
   ///////////////////////////
   if(ff<ff2)
   {
    printf("Case %I64d: %d/1\n",++tt,Ceil(ff));continue;
   }
   memset(xx,0,sizeof(xx));
   memset(yy,0,sizeof(yy));
   temp2=1;
        temp=getAns(a1,b1,a2,b2);
        y=temp,x=temp2;
        if(a1==0)
        {
    x=1;
            y=Ceil((double)b2/a2);
        }
        else
        {
    for(i=step-1;i>=1;i--)
    {
     if(yy[i]!=0)
     {
      x+=yy[i]*y; 
      swap(x,y);
     }
     if(xx[i]!=0)
     {
      x+=xx[i]*y;
      swap(x,y);
     }
    }
        }
       

        temp=gcd(x,y);
        x/=temp;
        y/=temp;
   if(!(     
    ((double)x/y<(double)a2/b2 && (double)x/y>(double)a1/b1 ) 
    || fabs((double)x/y-(double)a2/b2)<eps   
    ||   fabs((double)x/y-(double)a1/b1)<eps       
    ))
    swap(x,y);
        printf("Case %I64d: %I64d/%I64d\n",++tt,x,y);
    }
    return 0;
}
再问： 否则 整个不等式同时减去 d/c 得 d%c/c < [y-(d/c)*x]/x < [b-(d/c)*a]/a 怎么来的？ 为什么减完以后是那样的？