ACM 10814 10814 - Simplifying Fractions
作法:大數輾轉+除法
sagit所編寫的除法具有%的功用 所以整個拿來編寫 還蠻順利的
/***********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int Check(int a[],int b[],int lb,int lc)
{
int i;
for(i=lb-1; i>=0; i--)
{
if(a[i+lc]<b[i]) return 0;
if(a[i+lc]>b[i]) return 1;
}
return 1;
}
main()
{
int a,b,c,d,nn;
char x[50],y[50],z;
while(scanf("%d",&nn)==1)
{
while(nn--)
{
scanf("%s %c %s",x,&z,y);
int temp[50]={0};
int n=strlen(x),m=strlen(y),xx[50]={0},yy[50]={0};
int tempx[50]={0},tempy[50]={0};
for(a=0,c=n-1;c>=0;a++,c--)
tempx[a]=x[c]-48;
for(a=0,c=m-1;c>=0;a++,c--)
tempy[a]=y[c]-48;
for(a=49;a>=0;a--)
if(tempx[a]>tempy[a]) break;
if(a!=-1) /*將xx調整成較大的那個數*/
{
for(a=0,c=n-1;c>=0;a++,c--)
xx[a]=x[c]-48;
for(a=0,c=m-1;c>=0;a++,c--)
yy[a]=y[c]-48;
}
else
{
for(a=0,c=n-1;c>=0;a++,c--)
yy[a]=x[c]-48;
for(a=0,c=m-1;c>=0;a++,c--)
xx[a]=y[c]-48;
}
while(1)/*模擬展轉*/ /*拿較小的Y去除X*/
{
for(a=49;a>=0;a--)
if(xx[a]!=0) break;
for(b=49;b>=0;b--)
if(yy[b]!=0) break;
int la=a+2,lb=b+2,i,j;
for (i=la-lb; i>=0; i--)
{
while(Check(xx,yy,lb,i))
{
for(j=0;j<lb;j++)
{
xx[i+j]-=yy[j];
if(xx[i+j]<0)
{
xx[i+j]+=10;
xx[i+j+1]--;
}
}
}
}
int flag=1;
for(a=49;a>=0;a--)
if(xx[a]!=0)
{
flag=0;
break;
}
if(flag==1) break; /*整除了 OVER;*/
int temp[50]={0};/*將xx yy 對調*/
for(a=0;a<50;a++)
{
temp[a]=xx[a];
xx[a]=yy[a];
yy[a]=temp[a];
}
}
for(a=49;a>=0;a--) if(yy[a]!=0) break;
int la=n+1,lb=a+2,i,j;
for (i=la-lb; i>=0; i--)
{
while(Check(tempx,yy,lb,i))
{
temp[i]++;
for(j=0;j<lb;j++)
{
tempx[i+j]-=yy[j];
if(tempx[i+j]<0)
{
tempx[i+j]+=10;
tempx[i+j+1]--;
}
}
}
}
for(a=49;a>=0;a--)
if(temp[a]!=0)
{
for(b=a;b>=0;b--)
printf("%d",temp[b]);
printf(" / ");
break;
}
for(a=0;a<50;a++) temp[a]=0;
la=m+1;
for (i=la-lb; i>=0; i--)
{
while(Check(tempy,yy,lb,i))
{
temp[i]++;
for(j=0;j<lb;j++)
{
tempy[i+j]-=yy[j];
if(tempy[i+j]<0)
{
tempy[i+j]+=10;
tempy[i+j+1]--;
}
}
}
}
for(a=49;a>=0;a--)
if(temp[a]!=0)
{
for(b=a;b>=0;b--)
printf("%d",temp[b]);
printf("\n");
break;
}
}
}
return 0;
}