[HDU]1717 소수 화 점수 2-계수 원리

소수 화 점수 2
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2988    Accepted Submission(s): 1224
 
Problem Description
레이 는 수학 시간 에 선생님 의 말씀 을 듣 고 모든 소수 가 점수 로 표시 되 는 형식 이 라 고 말 했다.그 는 녹 기 시 작 했 고 곧 완성 되 었 다.그러나 그 는 또 하나의 문 제 를 생각 했다.어떻게 순환 소 수 를 점수 로 바 꿀 수 있 을 까?
일반 소 수 를 가장 간단 한 점수 로 만 들 수도 있 고 순환 소 수 를 가장 간단 한 점수 로 만 들 수도 있 는 프로그램 을 써 주세요.
 
Input
첫 번 째 줄 은 정수 N 으로 몇 개의 데이터 가 있 는 지 를 나타 낸다.
각 조 의 데 이 터 는 하나의 순수 소수,즉 정수 부분 이 0 이다.소수 의 자릿수 는 9 자 리 를 넘 지 않 고 순환 부분 은()로 묶는다.
 
Output
각 대응 하 는 소수 에 대해 가장 간단 한 점수 로 출력 하여 한 줄 을 차지한다.
 
Sample Input
3
0.(4)
0.5
0.32(692307)
 
Sample Output
4/9
1/2
17/52
 
Source
2007 성 경기 합숙 훈련 팀 연습 경기(2)
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  
1715  
1716  
1166  
1719  
1722  
 
문제 풀이:먼저 무한 순환 소수 분수 형식의 구조 방법 을 알 아야 한다.분 자 는 최소 순환 절 이 고 분 모 는 대응 하 는 자릿수 의 99.9 이다.만약 에 무한 순환 소수:0.568568...568 을 순환 절 로 한다 면 이 소수 의 점수 형식 은 568/999 이다.문제 에서 우 리 는 소수 의 유한 부분 과 무한 순환 부분 을 분리 하여 처리 하여 두 점 수 를 얻 었 다.게다가 간소화 하면 얻 는 것 이 바로 바 라 는 바 이다.
 
코드 는 다음 과 같 습 니 다:

 1 #include <cstdio>

 2 #include <cstring>

 3 

 4 typedef long long ll;

 5 

 6 const int LEN = 11;

 7 

 8 char num[LEN];

 9 ll a, b, c, d, e, f; //  a/b, c/d, e/f   

10 

11 ll diypow(int n) // 10 n  

12 {

13     ll ans = 1;

14     for(int i = 0; i < n; i++)

15         ans *= 10;

16     return ans;

17 }

18 

19 ll gcd(ll x, ll y) //     

20 {

21     while(x != y){

22         if (x > y)

23             x -= y;

24         else

25             y -= x;

26     }

27     return x;

28 }

29 

30 void cacnum() //      ，                       

31 {

32     a = b = c = d = 0;

33     int len1 = 0, len2 = 0; //len1 len2                         

34     int len = strlen(num);

35     for(int i = 0; i < len; i++){

36         if (num[i] == '('){

37             len2 = len - i - 2;

38             len1 = i - 2;

39             break;

40         }

41         if (i == len-1){

42             len1 = i - 1;

43         }

44     }

45     if (num[2] == '(')

46         sscanf(num, "0.(%I64d)", &c);

47     else

48         sscanf(num, "0.%I64d(%I64d)", &a, &c);  //       

49     if (len1 != 0)

50         b = diypow(len1); 

51     if (len2 != 0){

52         d = diypow(len2) - 1;

53         d *= diypow(len1);  //    

54     }

55 }

56 

57 int main()

58 {

59     //freopen("in.txt", "r", stdin);

60     int T;

61     scanf("%d", &T);

62     while(T--){

63         scanf("%s", num);

64         cacnum();

65         if (a != 0 && c != 0){ //              ，      

66             e = a * d / b + c;

67             f = d;

68         }

69         else if (a == 0){

70             e = c;

71             f = d;

72         }

73         else if (c == 0){

74             e = a;

75             f = b;

76         }

77         ll g = gcd(e, f); //               

78         printf("%I64d/%I64d
", e / g, f / g);

79     }

80     return 0;

81 }