Posted inc++ zerojudge

zerojudge a024. 最大公因數(GCD)

題目在 https://zerojudge.tw/ShowProblem?problemid=a024

一般來解這題就是用輾轉相除法, 所以會用到模數%來求餘數. 但是我們都知道電腦用模數計算時間比較久, 所以我想改用減法來寫看看. 減法要怎樣減比較快呢? 我就把減數用移位來變大, 左移一位就等於乘2,我就一直左移到比被減數還大後再右移一位就好.這樣就不用使用乘法.

unsigned int mod(unsigned a, unsigned int b){
	unsigned int temp=b;
	while(a>=temp)
		temp<<=1;
	temp>>=1;
	a=a-temp;
	if(a==0){
		printf("%d",b);
		return 0;
	}
	return a;
}
C++

當b>=a時也一樣,把參數顛倒就好了. 完整程式如下.

#include <iostream>

unsigned int mod(unsigned a, unsigned int b){
	unsigned int temp=b;
	while(a>=temp)
		temp<<=1;
	temp>>=1;
	a=a-temp;
	if(a==0){
		printf("%d",b);
		return 0;
	}
	return a;
}

int main(){
	unsigned int a,b;
	scanf("%d %d", &a, &b);

	while(a && b){
		if(a>=b){
			a=mod(a,b);
		}else{
			b=mod(b,a);
		}
	}
}
C++