2013年3月10日

UVa 10677 - Base Equality


#include <cstdio>
#include <string>
using std::string;

int find;

string turn(int n, int b) {
  char s[2];
  s[0] = n % b + '0';
  s[1] = 0;
  if (n) return turn(n / b, b) + s;
  return string(s);
}

void check(int b1, int b2, int n) {
  int i, s1 = 0, s2 = 0;
  string s = turn(n, b1);
  for (i = 0; s[i]; i++) {
    s1 = s1 * b1 + (s[i] - '0');
    s2 = s2 * b2 + (s[i] - '0');
  }
  if ((s2 / s1) * s1 == s2) {
    printf("%d\n", n);
    find = 1;
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int b1, b2, r1, r2;
    scanf("%d%d%d%d", &b1, &b2, &r1, &r2);
    find = 0;
    while (r2 >= r1 && !find)
      check(b1, b2, r2--);
    if (!find) puts("Non-existent.");
  }
  return 0;
}

沒有留言:

張貼留言