24h購物| | PChome| 登入
2013-06-29 21:32:17| 人氣816| 回應0 | 上一篇 | 下一篇

[UVA][數學] 11180 - Base i-1

推薦 0 收藏 0 轉貼0 訂閱站台

Problem F

Base i-1
 Input: Standard Input

Output: Standard Output

 

 

A complex system that works is invariably found
to have evolved from a simple system that works.

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=a+bi, where and and b are integers, and i is the square root of -1 (which means that i2=-1). A complex integer n written in base (i-1) is a sequence of digits (bi), writen right-to-left, each of which is either 0 or 1 (no negative or imaginary digits!), and the following equality must hold.

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 -1,000,000 to 1,000,000.

 

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

4
1 0
2 3
11 0
0 0
 
Case #1: 1
Case #2: 1011
Case #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



#include <stdio.h>

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;
}

我要檢舉
#11180#Base i-1#數學
台長： Morris

您可能對以下文章有興趣

人氣(816) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][遞迴] 11147 - KuPellaKeS BST
此分類上一篇:[UVA][黑白棋] 220 - Othello

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文