2012年12月15日

UVa 10780 - Again Prime? No Time.


#include <stdio.h>
#define S 10000

int prime[S], p[S], N;

void add(int n, int* rec) {
  int i;
  for (i = 0; i < N && p[i] <= n; i++)
    while (!(n % p[i]) && n > 1) {
      n /= p[i];
      rec[i]++;
    }
}

int main() {
  int i, j;
  for (i = 2; i < S; i++)
    if (!prime[i]) {
      p[N++] = i;
      for (j = i + i; j < S; j += i)
        prime[j] = 1;
    }
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int m, n, num[S] = {}, fac[S] = {}, flag = 1, min = 2e9;
    scanf("%d%d", &m, &n);
    add(m, num);
    for (i = 2; i <= n; i++)
      add(i, fac);
    for (i = 0; i < N && flag; i++)
      if (num[i] > fac[i]) flag = 0;
      else if (num[i] && fac[i] && fac[i] / num[i] < min) min = fac[i] / num[i];
    printf("Case %d:\n", C++);
    if (flag) printf("%d\n", min);
    else puts("Impossible to divide");
  }
  return 0;
}

沒有留言:

張貼留言