2011-06-10 20:47:44Morris
d646. I2A的陰謀
http://zerojudge.tw/ShowProblem?problemid=d646
內容 ：
I2A(IQ 200 Apple)是一種可怕的外星生物，
現在I2A軍團已經佔領了賢者之塔，
企鵝村已經派出吳企鵝來收這個爛攤子。
當吳企鵝來到賢者之塔的入口的時候，
發現居然被加裝了詭異的密碼鎖，怎麼用魔法炸都炸不掉。
所以吳企鵝只好乖乖解讀裡面的密碼。
現在解密的過程有一個關鍵：
「求兩二進位數的最大公因數」
吳企鵝現在想請你幫忙寫個程式來作這件工作。
現在I2A軍團已經佔領了賢者之塔，
企鵝村已經派出吳企鵝來收這個爛攤子。
當吳企鵝來到賢者之塔的入口的時候，
發現居然被加裝了詭異的密碼鎖，怎麼用魔法炸都炸不掉。
所以吳企鵝只好乖乖解讀裡面的密碼。
現在解密的過程有一個關鍵：
「求兩二進位數的最大公因數」
吳企鵝現在想請你幫忙寫個程式來作這件工作。
輸入說明
：
每個測資點僅一組測資，包含兩列長串二進位數。(值必定大於0)
(每列不超過1000000個字元)
(每列不超過1000000個字元)
輸出說明
：
請以二進位表示輸出這兩個數的最大公因數。
範例輸入 ：
1111111111111111111111111111111 1010101110011110101011101
範例輸出 ：
1
提示
：
共計兩個測資點，配分50％、50％
提示：I2A = 經典名著Introduction to algorithm之簡寫
出處
：
jack1
(管理：jack1)
作法 : 大數二進制輾轉
並不是將二進制轉十進制再做，而是直接做
藉由二進制的道理，大數處理只會有減法(我下面用補數去做減法)
並不會有除法的問題，至於它下面給的提示，我不懂就是了
作法 : 大數二進制輾轉
並不是將二進制轉十進制再做，而是直接做
藉由二進制的道理，大數處理只會有減法(我下面用補數去做減法)
並不會有除法的問題，至於它下面給的提示，我不懂就是了
/**********************************************************************************/
/* Problem: d646 "I2A的陰謀" from jack1 */
/* Language: C */
/* Result: AC (2ms, 250KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-06 11:24:33 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char x[1000001], y[1000001];
int s[2][1000001];
void binary_gcd(int in1, int in2, int s1, int s2) {
int flag = 0, a;
if(in1 == in2) { /*s1 s2 change to (s1 > s2)*/
for(a = 0; a <= in1; a++)
if(s[s1][a] > s[s2][a]) {flag = 2; break;}
else if(s[s1][a] < s[s2][a]) {flag = 1; break;}
if(flag == 1) {
int t;
t = s1, s1 = s2, s2 = t;
}
}
if(in1 < in2) {
int t;
t = s1, s1 = s2, s2 = t;
t = in1, in1 = in2, in2 = t;
}
if(in2 == -1) {
a = 0;
while(s[s1][a] == 0) a++;
for(; a <= in1; a++) putchar(s[s1][a] + '0');
return ;
}
if(in1 == in2 && flag == 0) { /*s1 == s2*/
a = 0;
while(s[s1][a] == 0) a++;
for(; a <= in1; a++) putchar(s[s1][a] + '0');
return ;
}
else if(s[s1][in1] == 0 && s[s2][in2] == 0) {
binary_gcd(in1-1, in2-1, s1, s2), putchar('0');
}
else if(s[s1][in1] == 0 && s[s2][in2] == 1) {
binary_gcd(in1-1, in2, s1, s2);
}
else if(s[s1][in1] == 1 && s[s2][in2] == 0) {
binary_gcd(in1, in2-1, s1, s2);
}
else { /*s1-s2 s2*/
int b;
s[s1][in1] ++;
for(a = in1, b = in2; a >=0 && b >=0; a--, b--) {
s[s1][a] += ! s[s2][b];
if(s[s1][a] > 1 && a != 0) {
s[s1][a-1] += s[s1][a]/2;
s[s1][a] %= 2;
}
}
while(a >= 0) {
s[s1][a] ++;
if(s[s1][a] > 1 && a != 0) {
s[s1][a-1] += s[s1][a]/2;
s[s1][a] %= 2;
}
a--;
}
s[s1][0] %= 2;
binary_gcd(in1, in2, s1, s2);
}
}
main() {
while(scanf("%s %s", x, y) == 2) {
int a, l = strlen(x);
for(a = 0; a < l; a++) s[0][a] = x[a] - '0';
l = strlen(y);
for(a = 0; a < l; a++) s[1][a] = y[a] - '0';
binary_gcd(strlen(x)-1, strlen(y)-1, 0, 1), puts("");
}
return 0;
}
上一篇：d645. 輪下亡魂
下一篇：d652. 貪婪之糊