注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SGU106[The equation]  

2010-08-26 15:11:29|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

数学题。扩展欧几里得解模同余方程。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-26

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

#include <math.h>

using namespace std;

 

#define lli long long int

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define ceil_div(a,b) ceil(double(a)/double(b))

#define floor_div(a,b) floor(double(a)/double(b))

 

lli gcd(lli a,lli b,lli& x,lli& y)

{

    //ax+by=gcd(a,b)

    if (b==0)

    {

       x=1,y=0;

       return a;

    }

    else

    {

        lli g=gcd(b,a%b,y,x);

        //b*y+a%b*x=gcd(b,a%b)=gcd(a,b)

        // b*y+a%b*x

        //=b*y+(a-a/b*b)*x

        //=b*y-a/b*b*x+a*x

        //=a*x+b*(y-a/b*x)

        y-=a/b*x;

        return g;

    }

}

lli get_answer(lli a,lli b,lli c,lli x1,lli x2,lli y1,lli y2)

{

    //ax+by+c=0

    if (!(x1<=x2&&y1<=y2)) return 0;

    else if (a==0&&b==0)

         return (c==0)*(x2-x1+1)*(y2-y1+1);

    else if (a==0)

    {

         lli y=-c/b;

         return ((b*y+c==0)&&(y1<=y&&y<=y2))*(x2-x1+1);

    }

    else if (b==0)

    {

         lli x=-c/a;

         return ((a*x+c==0)&&(x1<=x&&x<=x2))*(y2-y1+1);

    }

    else

    {

        //a*x = c (mod b)

        lli x,y,g;

        g=gcd(a,b,x,y);//ax+by=g

        if (c%g==0)

        {

           a/=g,b/=g,c/=g;//ax+by=1

           x*=-c,y*=-c;//ax*(-c)+by*(-c)=-c          

           //set of root = {(x+b*k,y-a*k)}          

           lli rxa,rxb;

           if (b>0) rxa=ceil_div(x1-x,b),rxb=floor_div(x2-x,b);

           else rxa=ceil_div(x2-x,b),rxb=floor_div(x1-x,b);

           lli rya,ryb;

           if (a<0) rya=ceil_div(y-y1,a),ryb=floor_div(y-y2,a);

           else rya=ceil_div(y-y2,a),ryb=floor_div(y-y1,a);

           lli ra,rb;

           ra=max(rxa,rya);

           rb=min(rxb,ryb);

           if (ra<=rb) return (rb-ra+1);

           else return 0;

        }

        else return 0;

    }

}

 

int main()

{

    lli a,b,c,x1,x2,y1,y2;

    cin>>a>>b>>c>>x1>>x2>>y1>>y2;

    cout<<get_answer(a,b,c,x1,x2,y1,y2)<<endl;

}

 

  评论这张
 
阅读(456)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018