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

Re:测试数据是不是错了?

Posted by 2_020310620 at 2006-02-05 16:32:30 on Problem 1061
In Reply To:Re:测试数据是不是错了? Posted by:encapsulation at 2006-02-05 15:44:27
#include <math.h>
#include <stdio.h>
int gcd(int a,int b)
{
	int x=1;
	int y=1;
	if (b>a)
	{
		x=b;
		y=a;
	}
	else
	{
		x=a;
		y=b;
	}
	while (y)
	{
		a=y;
		y=x%y;
		x=a;
	}
	return x;
}
int fun(int a,int b)
{
	int temp=1;
	int Q0=1;
	int Q1=0;
	int Q2=1;
	int q=0;
	int count=0;
 	while (b!=1)
	{
		q=a/b;
		temp=a;
		Q2=q*Q1+Q0;
		a=b;
		b=temp%b;
		count++;
		Q0=Q1;
		Q1=Q2;
	}
	if (count%2==0)
		Q2=-Q2;
	return Q2; 
}
void main()
{
	int m=0;
	int n=0;
	int x=0;
	int y=0;
	int L=0;
	int temp=0;
    int nGcd=1; 
    scanf("%d%d%d%d%d",&x,&y,&m,&n,&L);
    if (m==n) 
	{
		printf("Impossible\n");
		return;
	}
	nGcd=gcd((int)abs(m-n),L);
	if ( ((int)abs(x-y))%nGcd!=0 )
	{
		printf("Impossible\n");
		return;
	}
	if (m-n>0)
	{
		L/=nGcd;
		x=(y-x)/nGcd;
		m=(m-n)/nGcd;
		temp=fun(m,L);
		temp*=x;
		while (temp<0)
			temp+=L;
		if (temp>0)
		{
			while (temp>0)
				temp-=L;
			temp+=L;
		}
	}
	else if (m-n<0)
	{
		L/=nGcd;
		x=(x-y)/nGcd;
		m=(n-m)/nGcd;
		temp=fun(m,L);
		temp*=x;
		while (temp<0)
			temp+=L;
		if (temp>0)
		{
			while (temp>0)
				temp-=L;
			temp+=L;
		}
	}
    printf("%d\n",temp);
}

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