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:我1000组也就那2组没过,可还是WA

Posted by Gyber at 2011-11-08 08:03:29 on Problem 1061
In Reply To:楼主给力,1000组我有2组没过,结果poj ac 了 Posted by:lmm333 at 2011-06-29 21:42:35
#include<iostream>
using namespace std;
__int64 T,K;
__int64 gcd(__int64 a,__int64 b)
{
    if(!(a%b))
        return b;
    else
        return gcd(b,a%b);
}
void exELD(__int64 a,__int64 b)
{
    if(b==0)
        {
        T=1;
        K=0;
        return ;
        }
    exELD(b,a%b);
    __int64 tmp=T;
    T=K;
    K= tmp - a/b*K;
}
int main()
{
    __int64 a,b,c,d,x,y,m,n,L,t;
while(cin>>x)
{
    cin>>y>>m>>n>>L;
    x%=L;
    y%=L;
    m%=L;
    n%=L;
    if(m < n)
        {
        swap(m,n);
        swap(x,y);
        }
    a=(m-n);
    b=L;
    c=(y-x+L)%L;
    d=gcd(a,b);
    if(c%d)
        {
        cout<<"Impossible"<<endl;
        continue;
        }
    
    a/=d;
    b/=d;
    
    exELD(a,b);
    T*=c/d;
    K*=c/d;
    if(T >= 0)
        {
        t=T/b;
        T-=t*b;
        K+=t*a;
        if(T == 0)
            {
            T+=b;
            K-=a;
            }
        }
    else
        {
        t=(abs(T)+b-1)/b;
        T+=t*b;
        K-=t*a;
        }
    cout<<T<<endl;
}
    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