UVa 10375 Choose and divide

简单的分解质因数约分
  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 
  5 const int MAXN = 10000 + 10;
  6 
  7 bool Prime[MAXN];
  8 
  9 int aaa[5];
 10 int bbb[5];
 11 int num[2][MAXN];
 12 
 13 void GetPrime()
 14 {
 15     memset( Prime, true, sizeof(Prime) );
 16     Prime[0] = false ;
 17     Prime[1] = false ;
 18     for ( int i = 2; i < MAXN; i++ )
 19         if ( Prime[i] )
 20         {
 21             for ( int j = i * i; j < MAXN; j += i )
 22                 Prime[j] = false;
 23         }
 24     return;
 25 }
 26 
 27 int cmp( const void *a, const void *b )
 28 {
 29     return *(int *)a - *(int *)b;
 30 }
 31 
 32 int max( int a, int b )
 33 {
 34     return a > b ? a : b;
 35 }
 36 
 37 int min( int a, int b )
 38 {
 39     return a < b ? a : b;
 40 }
 41 
 42 void show()
 43 {
 44     for ( int i = 0; i < 20; i++ )
 45        printf("%d ", num[0][i]);
 46     puts("\n---------------------");
 47     for ( int i = 0; i < 20; i++ )
 48        printf("%d ", num[1][i]);
 49     puts("\n----------------");
 50     return;
 51 }
 52 
 53 int main()
 54 {
 55     GetPrime();
 56     int p, q, r, s;
 57     while ( scanf( "%d%d%d%d", &p, &q, &r, &s ) != EOF )
 58     {
 59         memset( num, 0, sizeof(num) );
 60 
 61         aaa[0] = p;
 62         aaa[1] = s;
 63         aaa[2] = r - s;
 64         bbb[0] = q;
 65         bbb[1] = r;
 66         bbb[2] = p - q;
 67         qsort( aaa, 3, sizeof(int), cmp );
 68         qsort( bbb, 3, sizeof(int), cmp );
 69 
 70 //        for ( int i = 0; i < 3; i++ ) printf("%d %d\n", aaa[i], bbb[i]);
 71 
 72         int down, up;
 73         for ( int i = 0; i < 3; i++ )
 74         {
 75             int xxx;
 76             if ( aaa[i] == bbb[i] ) continue;
 77             else if ( aaa[i] > bbb[i] )
 78             {
 79                 down = bbb[i] + 1;
 80                 up = aaa[i];
 81                 xxx = 0;
 82             }
 83             else
 84             {
 85                 down = aaa[i] + 1;
 86                 up = bbb[i];
 87                 xxx = 1;
 88             }
 89             for ( int i = down; i <= up; i++ )
 90             {
 91                 int tp = i;
 92     //            printf("tp = %d\n", tp);
 93                 int yyy = 2;
 94                 while ( tp != 1 )
 95                 {
 96                     if ( Prime[yyy] && tp % yyy == 0 )
 97                     {
 98       //                  printf("yyy = %d\n", yyy);
 99                         tp /= yyy;
100                         ++num[xxx][yyy];
101                     }
102                     else ++yyy;
103                 }
104             }
105         }
106 
107         for ( int i = 2; i < MAXN; i++ )
108         if ( Prime[i] )
109         {
110             if ( num[0][i] > num[1][i] )
111             {
112                 num[0][i] -= num[1][i];
113                 num[1][i] = 0;
114             }
115             else
116             {
117                 num[1][i] -= num[0][i];
118                 num[0][i] = 0;
119             }
120         }
121 
122   //      show();
123 
124         double ans = 1.0;
125         for ( int i = 2; i < MAXN; i++ )
126             if ( Prime[i] )
127             {
128                 int fenzi = 1, fenmu = 1;
129                 for ( int j = 0; j < num[0][i]; j++ ) fenzi *= i;
130                 for ( int j = 0; j < num[1][i]; j++ ) fenmu *= i;
131                 ans *= (double)fenzi/fenmu;
132             }
133 
134         printf( "%.5lf\n", ans );
135     }
136     return 0;
137 }