Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这就是一道扩展欧几里德 就不知哪里错 郁闷哦

Posted by 1325784226 at 2012-05-01 20:28:40 on Problem 2115
#include <cstdio>
__int64 pow(__int64 a,__int64 b)
{
	__int64 s=1;
	for(__int64 i=0; i<b; i++)
		s *= a;
	return s;
}

__int64 exGcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	__int64 r = exGcd(b,a%b,x,y);
	__int64 t = x;
	x = y;
	y = t - a/b * y;
	return r;
}

int main()
{
	//freopen("input.txt","r",stdin);
	__int64 a,b,c,k;
	__int64 x,y;
	__int64 p;
	__int64 d;
	__int64 ab;
	__int64 r;
	while(scanf("%I64d %I64d %I64d %I64d",&a,&b,&c,&k)!=EOF && a != 0 && b!=0 && c !=0 && k != 0)
	{
		p = pow(2,k);
		ab = b - a;
		d = exGcd(c,-p,x,y);
		if(ab % d !=0)
			printf("FOREVER\n");
		else
		{
			r = ab / d;
			__int64 xx = r*x;
			if(xx < 0)
				xx = (xx % (p/d) + (p/d))% (p/d);
			
			printf("%I64d\n",xx);
		}
		
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator