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

I got it! First AC!

Posted by yc5_yc at 2012-06-22 13:49:02 on Problem 1061
In Reply To:线性同余送分题 Posted by:yc5_yc at 2012-06-17 12:20:33
#include <cstdio>
#include <algorithm>
using namespace std;
struct tri
{
    long long d,x,y;
};
long long x,y,m,n,L;
long long l,r,mod;
long long opt(long long a,long long b)
{
    if(a<0)
    {
        long long Ch=(0-a)/b;
        a+=Ch*b;
        if(a<0) a+=b;
    }
    return a%b;
}
tri EE(long long x,long long y)
{
    tri a;
    a.d=x,a.x=1,a.y=0;
    if(y==0) return a;
    a=EE(y,opt(x,y));
    swap(a.x,a.y);
    a.y-=(x/y)*a.x;
    return a;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
    l=m-n; r=y-x; mod=L;
    tri a=EE(l,mod);
    if(opt(r,a.d)!=0)
        puts("Impossible");
    else
    {
        long long X=opt(a.x*(r/a.d),mod);
        if(mod-X<=(a.d-1)*(mod/a.d))
            x=0;
        printf("%lld\n",X);
    }
    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