程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2115 C Looooops 擴展歐幾裡得

poj 2115 C Looooops 擴展歐幾裡得

編輯:C++入門知識

poj 2115 C Looooops 擴展歐幾裡得


題意:

在while(x=a;x!=b;x+=c) statement;中,問statement會被執行多少次,計算在2^k下進行。

思路:

等價於計算同余式a+c*x=b(mod2^k)用擴展歐幾裡得算法。設g=gcd(a,b)在計算a*x+b*y=g過程中,x的結果可以用b/g調整,y的結果可以用a/g調整,因為a*(b/g)==b*(a/g)。

代碼:

//poj 2115
//sep9
#include
using namespace std;


void gcd(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y)
{
	if(b==0){
		d=a,x=1,y=0;
	}
	else{											//a/b==(a-a%b)/b
		gcd(b,a%b,d,y,x);//by+(a%b)x=d ==> ax+b(y-x(a-a%b)/b))=by+(a%b)x=d
		y-=x*(a/b);
	}
}

int main()
{
	__int64 a,b,c,A,B,C,k,d,x,y;
	while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k)==4){
		if(a==0&&b==0&&c==0&&k==0)
			break;	
		k=1LL<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved