[UVA][數學] 11180 - Base i-1
Problem F
Base i-1
Input: Standard Input
Output: Standard Output
|
A complex system that
works is invariably found |
John Gaule
Everyone knows about base-2
(binary) integers and base-10 (decimal) integers, but what about base i-1?
A complex integer n has the form
n = b0 + b1(i-1) + b2(i-1)2 + b3(i-1)3 + ...
The cool thing is that every complex integer has a unique base-(i-1) representation, with no minus sign required. Your task is to find this representation.
Input
The first line of input gives the
number of cases, N (at most 20000). N test cases follow. Each one
is a line containing a complex integer a+bi as
a pair of integers, a and b. Both a
and b will be in the range from
Output
For each test case, output one line containing "Case #x:" followed by the same complex integer, written in base i-1 with no leading zeros.
Sample Input Output for Sample Input
41 02 311 00 0 |
Case #1: 1Case #2: 1011Case #3: 111001101
Case #4: 0 |
Problem setter: Igor Naverniouk
Special Thanks: Shahriar Manzoor
題目描述：
複數的二進制數表示法
題目解法：
考慮將 (i-1) 的冪次展開看看,
(i-1)^0 = 1
(i-1)^1 = i-1
(i-1)^2 = -2i
(i-1)^3 = 2+2i
(i-1)^4 = -4
(i-1)^5 = -4i+4
(i-1)^6 = 8i
(i-1)^7 = -8-8i
(i-1)^8 = 16 ...
可以發現以 a+bi 的形式去觀察, 只會在 (i-1)^0 次時 a+b 是奇數。
因此可以用類似轉換二進制的形式得到,
if(a+b is odd) convert(((a-1)+bi) / (i-1)), print 1
else convert((a+bi) / (i-1)), print 0
void binary(int a, int b) {
if(a == 0 && b == 0)
return;
int c = ((a+b)%2+2)%2;
if(c == 1)
a--;
binary((-a+b)/2, (-a-b)/2);
printf("%d", c);
}
int main() {
int testcase, cases = 0, a, b;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &a, &b);
printf("Case #%d: ", ++cases);
if(a == 0 && b == 0) puts("0");
else {
binary(a, b);
puts("");
}
}
return 0;
}