学步园

UVA_10717

    枚举桌腿的选择，然后求出最小公倍数之后再进行相应的计算、更新即可。

#include<stdio.h>
#include<string.h>
#define MAXN 60
#define MAXT 15
int N, T, a[MAXN], t[MAXT];
long long int low[MAXT], high[MAXT];
long long int gcd(long long int x,long long int y)
{
return y == 0 ? x : gcd(y, x % y);
}
int init()
{
int i;
    scanf("%d%d", &N, &T);
if(!N && !T)
return 0;
for(i = 0; i < N; i ++)
        scanf("%d", &a[i]);
for(i = 0; i < T; i ++)
        scanf("%d", &t[i]);
return 1;
}
void solve()
{
int i, j, k, p, q;
long long int temp, ans;
    memset(high, 0x3f, sizeof(high));
    memset(low, 0, sizeof(low));
for(i = 0; i < N; i ++)
for(j = i + 1; j < N; j ++)
for(k = j + 1; k < N; k ++)
for(p = k + 1; p < N; p ++)
                {
                    ans = a[i];
                    temp = a[j], ans = ans / gcd(ans, temp) * temp;
                    temp = a[k], ans = ans / gcd(ans, temp) * temp;
                    temp = a[p], ans = ans / gcd(ans, temp) * temp;
for(q = 0; q < T; q ++)
                    {
if(ans < t[q] && t[q] - t[q] % ans > low[q])
                            low[q] = t[q] - t[q] % ans;
if((ans - t[q] % ans) % ans + t[q] < high[q])
                            high[q] = (ans - t[q] % ans) % ans + t[q];
                    }
                }
for(i = 0; i < T; i ++)
        printf("%lld %lld\n", low[i], high[i]);
}
int main()
{
while(init())
    {
        solve();
    }
return 0;
}