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

进入前10000名纪念~~

Posted by shmr0077 at 2011-04-28 15:38:52 on Problem 1061
AC的第49题~~贴代码留念~~
#include<iostream>
#include<cstdio>
using namespace std;

long long ext_gcd(long long x,long long y,long long &px,long long &py){
	long long lastp=1,lastq=0,p=0,q=1,m,tmp,tmpp,tmpq;
	while(y!=0){
		m=x/y;
		tmpp=lastp-p*m;tmpq=lastq-q*m;tmp=x%y;
		x=y;lastp=p;lastq=q;
		y=tmp;p=tmpp;q=tmpq;
	}
	px=lastp;py=lastq;
	return x;
}

int main(){
	//freopen("in.txt","r",stdin);
	
	long long x,y,m,n,l;
	long long k,ps,pt,px,c,gcdkl;
	while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!=EOF){
		if(m==n)printf("Impossible\n");
		else{
			k=(m-n+l)%l;c=(y-x+l)%l;
			gcdkl=ext_gcd(k,l,ps,pt);
			if(c%gcdkl)printf("Impossible\n");
			else{
				px=ps*c/gcdkl;
				if(px>0)px%=(l/gcdkl);
				else px=(px%(l/gcdkl)+l/gcdkl);
				printf("%lld\n",px%l);
			}
		}
	}
	
	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