1823227_ac_453ms_64k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>

int dd[10001];
int ns, nc;

int get_gcd(int a, int b)
{
    int r;
    if (b == 0)
    {
        return a;
    }
    for (r = a % b; r != 0; r = a % b)
    {
        a = b;
        b = r;
    }
    return b;
}

void main()
{
    int ratio[21];
    int n, k, i, j, a, b, aa, bb, min;
    int sig, gcd;

    scanf("%d", &ns);
    for (nc = 1; nc <= ns; nc++)
    {
        if (nc != 1)printf("\n");
        printf("Scenario #%d:\n", nc);
        scanf("%d", &n);
        for(i = 0; i < n; i++) 
          scanf("%d", &ratio[i]);
        scanf("%d", &k);
        while(k--) {
            scanf("%d %d", &aa, &bb);
            sig = 1;
        for(i = 1; i < 10001; i++) dd[i] = 0;
            a = aa;b = bb;
            if(aa > bb) 
            {
                a = bb;
                b = aa;
            } 
            gcd = get_gcd(aa, bb);
            a /= gcd;
            b /= gcd;
            for(i = 0, min = ratio[0]; i < n; i++) 
                if(min > ratio[i])
                    min = ratio[i];
            dd[1] = 1;
            for(i = 0; i < n; i++) 
             dd[ratio[i] / min] = 1;
             for(i = 0; i < n; i++) 
                for(j = 0; j < n; j++) 
                    if(j != i && ratio[j] % ratio[i] == 0) 
                        dd[ratio[j] / ratio[i]] = 1;
                    
                 for(i = 1; i < 10001; i++) 
                if(dd[i] == 1) 
                    for(j = 2; j <= i; j++) 
                    {
                        if( i * j > 10000) 
                        break;
                        if(dd[j] == 1) 
                            dd[i * j] = 1;
                    }
                if(dd[a] == 1 && dd[b] == 1) sig = 0;
                else 
                for(i = 2; ; i++) 
                {
                    if(b * i > 10000) 
                        break;
                    if(dd[a * i] == 1 && dd[b * i]==1) 
                    {
                        sig = 0;
                        break;
                    }
                }
           if(sig == 0) 
               printf("Gear ratio %d:%d can be realized.\n", aa, bb);
            else 
                printf("Gear ratio %d:%d cannot be realized.\n", aa, bb);
             }
    }
}