一开始以为是线性规划的题目,看了网上的提示说是求模线性方程。用拓展欧几里得算法可以得出原方程的一个解。然后就可以根据这个解判断在所给的区间里有几个解。题目比较纠结的地方是边界问题的判断,花了很多时间。以后要多做题才能更快地考虑好边界问题。
由ax+by+c = 0有ax+by = -c,两边取模b得到
ax+by ≡ -c (mod b) 推出 ax ≡ -c (mod b)
模线性方程有解当且仅当gcd(a,b) | -c,有解的情况下方程对模-c有d个不同的解,d=gcd(a,b)
根据拓展欧几里得算法可以算出x0, y0使得d = a*x0+b*y0
则x =  x0*(-c/d), y = y0*(-c/d)为原方程ax+by+c=0的一个解
则方程的所有解为x = x0*(-c/d) + i*(b/d), y = y0*(-c/d) - i*(a/d)
计算所有的i使得解在所给区间内的个数即可。

#include <stdio.h>

typedef 
struct tagNode {
    
long long d; long long x; long long y;
} Node;

void swap(long long* a, long long* b) {
    
long long t = *a;
    
*= *b;
    
*= t;
}

Node euclid(
long long a, long long b) {
    Node t;
    
if (!b) {
        t.d 
= a; t.x = 1; t.y = 0;
        
return t;
    }
    t 
= euclid(b, a % b);
    Node t1;
    t1.d 
= t.d; t1.x = t.y; t1.y = t.x-(a/b)*t.y;
    
return t1;
}

int main(void) {
    
long long a, b, c;
    
long long x1, x2, y1, y2;
    scanf (
"%I64d%I64d%I64d"&a, &b, &c);
    c 
= -c;
    scanf (
"%I64d%I64d%I64d%I64d"&x1, &x2, &y1, &y2);
    
long long count = 0;
    
if (a==0 && b==0) {
        
if (c==0) {
            count 
= (x2-x1+1)*(y2-y1+1);
        }
    } 
else if (a==0) {
        
if (c%b==0 && c/b>=y1 && c/b<=y2) {
            count 
= x2-x1+1;
        }
    } 
else if (b==0) {
        
if (c%a==0 && c/a>=x1 && c/a<=x2) {
            count 
= y2-y1+1;
        }
    } 
else {  //如果a,b都不为0,用拓展欧几里得算出一个解
        Node t = euclid(a, b);
        
if (c % t.d == 0) {
            t.x 
*= c/t.d;
            t.y 
*= c/t.d;
            
long long lx, rx, ly, ry;
            lx 
= (x1<=t.x || (x1-t.x)*t.d%b==0? (x1-t.x)*t.d/b : (x1-t.x)*t.d/b+1;
            rx 
= (x2>=t.x || (t.x-x2)*t.d%b==0? (x2-t.x)*t.d/b : (x2-t.x)*t.d/b-1;
            ly 
= (y1<=t.y || (y1-t.y)*t.d%a==0? (t.y-y1)*t.d/a : (t.y-y1)*t.d/a-1;
            ry 
= (y2>=t.y || (t.y-y2)*t.d%a==0? (t.y-y2)*t.d/a : (t.y-y2)*t.d/a+1;
            
if (lx > rx) {
                swap(
&lx, &rx);
            }
            
if (ly > ry) {
                swap(
&ly, &ry);
            }
            
if (lx <= ry && ly <= rx) { //求出两个区间交集的元素个数
                long long max = (lx>ly) ? lx : ly;
                
long long  min = (rx<ry) ? rx : ry;
                count 
= min-max+1;
            }
        }
    }
    printf (
"%I64d\n", count);
    
return 0;
}


posted on 2010-05-01 13:10 Willing 阅读(1276) 评论(2)  编辑 收藏 引用 所属分类: ACM
Comments
  • # re: SGU-106 The Equation
    Strayer
    Posted @ 2011-01-10 01:20
    感谢..受教了...  回复  更多评论   
  • # re: SGU-106 The Equation
    lzqxh@126.com
    Posted @ 2012-07-08 22:37
    请楼主仔细测试一下。。。
    10 11 3
    5 6
    -10 10
    这个数据,你的程序跑出来的结果是1,但是答案显然应该是0
    if (lx > rx) {
    swap(&lx, &rx);
    }
    if (ly > ry) {
    swap(&ly, &ry);
    }
    这个交换是错误的。。。不过我卡了几个小时的程序加上这两句话也AC了。。囧  回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理