Solution 4553. Convert to Fraction (vn.spoj.pl)

Link đề bài: http://vn.spoj.pl/problems/CTF/

Đề bài:
4553. Convert to Fraction
Mã bài: CTF



Mọi số hữu tỉ đều có thể biểu diễn dưới dạng phân số hoặc dạng thập phân vô hạn tuần hoàn.

* (1) Biểu diễn dạng phân số của một số hữu tỉ là a/b, với a, b là các số nguyên, b khác 0, và ước chung lớn nhất của a và b bằng 1 (để đảm bảo phân số tối giản).
* (2) Biểu diễn dạng thập phân vô hạn tuần hoàn của một số hữu tỉ là x.y(z), với x, y, z là các số nguyên (có thể có số 0 ở đầu). Trong biểu diễn này, (z) thể hiện cho phần tuần hoàn.

Biểu diễn phải đảm bảo trước tiên là y có ít chữ số nhất có thể, sau đó là z có ít chữ số nhất có thể. Ví dụ, biểu diễn 0.12(1212) là không hợp lệ; biểu diễn đúng là 0.(12).

Lưu ý rằng biểu diễn có thể không có phần y, và nếu số hữu tỉ có phần thập phân hữu hạn thì (z) = (0). Ví dụ, 1/3 = 0.(3), 20/13 = 1.(538461), 557/495 = 1.1(25), 5/1 = 5.(0), 3/2 = 1.5(0) …

Cho biểu diễn dạng thập phân vô hạn tuần hoàn của một số số hữu tỉ, hãy tìm biểu diễn dạng phân số của chúng.
Dữ liệu

Dòng đầu ghi T là số lượng số hữu tỉ cần tính toán. T dòng tiếp theo, mỗi dòng ghi một số hữu tỉ được biểu diễn dưới dạng thập phân vô hạn tuần hoàn, theo định dạng như mô tả ở (2).
Kết quả

Gồm T dòng, mỗi dòng ghi biểu diễn dạng phân số của số hữu tỉ tương ứng, theo định dạng như mô tả ở (1).
Giới hạn

Trong 50% số điểm:

* 0 ≤ x ≤ 10^3
* 0 ≤ y ≤ 10^3
* 0 ≤ z ≤ 10^3

Trong 50% số điểm còn lại:

* 0 ≤ x ≤ 10^10
* 0 ≤ y ≤ 10^10
* 0 ≤ z ≤ 10^10

Ví dụ

Dữ liệu

5
0.(3)
1.(538461)
1.1(25)
5.(0)
1.5(0)

Kết quả

1/3
20/13
557/495
5/1
3/2

Được gửi lên bởi: Race with time
Ngày: 2009-07-04
Thời gian chạy: 1s
Giới hạn mã nguồn: 50000B
Ngôn ngữ cho phép: Tất cả ngoại trừ: TCL SCALA ERL TECS JS
Nguồn bài: Own









Algorithm:

Đặt k=Mu(10,number(y))

x.y(z)-->xy.(z)/k=(xy*k+z)/(k-1)

Code:

#include
// #include
#include
#include
// #include


char s[255],Test[5];
long long int ng,th,tp;
int sotp,soth,T;
long long int tu,mau,uc;

long long int Nguyen(char s[255]);
long long int TuanHoan(char s[255]);
long long int ThapPhan(char s[255]);
long long int Mu(int k);
int Number(long long int k);
long int GCD(long long int a,long long int b);


int main()
{
gets(Test);
T=atoi(Test);
int i;
for(i=0;i
{
gets(s);
ng=Nguyen(s);
// printf("%lld ",ng);
tp=ThapPhan(s);
// printf("%lld ",tp);
th=TuanHoan(s);
// printf("%lld ",th);
sotp=Number(tp);
// printf("%d ",sotp);
soth=Number(th);
// printf("%d ",soth);

ng=ng*Mu(sotp)+tp;
if(th==0)
{
tu=ng;
mau=Mu(sotp);
uc=GCD(tu,mau);
tu=tu/uc;
mau=mau/uc;
printf("%lld",tu);
printf("%s","/");
printf("%lld ",mau);
}
else
{
tu=ng*(Mu(soth)-1)+th;
mau=Mu(sotp)*(Mu(soth)-1);
// printf("mau=%lld ",mau);
uc=GCD(tu,mau);
tu=tu/uc;
mau=mau/uc;
printf("%lld",tu);
printf("%s","/");
printf("%lld ",mau);
}
// getch();
}
return 0;
}
long int GCD(long long int a,long long int b)
{
if(a%b==0) return b;
return GCD(b,a%b);
}

int Number(long long int k)
{
if(k==0) return 0;
int kq=0;
while(k!=0)
{
kq++;
k/=10;
}
return kq;
}

long long int Mu(int k)
{
long long int kq=1;
int i;
for(i=1;i<=k;i++) kq*=10;
return kq;
}
long long int Nguyen(char s[255])
{
long long int kq=0;
int i=0;
while((i
{
kq=kq*10+(s[i]-48);
i++;
}
return kq;
}
long long int ThapPhan(char s[255])
{
long long int kq=0;
int i=0;
while((i
i++;
while((i
{
kq=kq*10+(s[i]-48);
i++;
}
return kq;
}
long long int TuanHoan(char s[255])
{
long long int kq=0;
int i=0;
while((i
i++;
while((i
{
kq=kq*10+(s[i]-48);
i++;
}
return kq;
}

Solution trên chỉ đạt 50 điểm. Muốn 100 điểm xử lý số lớn.