- 浏览: 308741 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
KIDx的解题报告
题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=106
题意:求ax + by + c = 0在[x1, x2], [y1, y2]区间内有多少组解?
解析:
①令c = -c有ax + by = c,可用扩展欧几里德解方程解出特解
当然要先考虑a = 0, b = 0, c = 0的情况进行特判
例如:a = 0, b = 1, c = 3,x∈[x1, x2], y∈[3, 4]
即可得知有方程有x2-x1+1个解,因为x可以区间内任意,且y=3这个解在区间内,其他情况同理了
②然后就是关键了,用的是扩展欧几里德通解式:(设一整数k,x0为x的特解)
1、x1 <= x0+k*b <= x2
2、y0 = (c - a*x0) / b
3、y1 <= y0+k'*b <= y2
解出k和k'的范围[s, e]!
注意了,例如解x1 <= x0+k*b:
当b<0时两边同时除以b,<=要变成>=号
--->k <= (x1-x0) / b
然后最关键就是除不尽应该向什么方向舍入?
区间[s, e]的舍入方向:
正数s, e的情况:
可见s = (x1-x0)/b还要+1,e直接除即可
负数s, e的情况:
可见e = (x1-x0)/b还要-1,s直接除即可
③最后得到x的k的范围[s1, e1], y的k'的范围[s2, e2]
因为x增加必然导致y减小,所以有:
举个例子,如图所示:令-e2作为s2,令-s2作为e2,答案为[-e2, e1]
所以答案ans = min (e1, e2') - max (s1, s2') + 1;
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <map>
#include <algorithm>
#include <math.h>
using namespace std;
#define M 1005
#define LL long long
LL gcd (LL a, LL b)
{
return b ? gcd (b, a%b) : a;
}
void Egcd (LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1, y = 0;
return ;
}
LL tp;
Egcd (b, a%b, x, y);
tp = x;
x = y;
y = tp - a/b*y;
}
LL cal (LL f, LL n, int key) //处理舍入问题
{
if (f % n == 0) return f/n;
if (key == 0)
{
if (f * n < 0) return f/n;
return f/n+1;
}
if (f * n < 0) return f/n-1;
return f/n;
}
LL a, b, c;
LL solve (LL &x1, LL &x2, LL &y1, LL &y2)
{
LL d, x, y, s1, e1, s2, e2;
c = -c;
/***********************特判***********************/
if (a == 0 && b == 0 && c == 0)
return (x2-x1+1) * (y2-y1+1);
if (a == 0 && b == 0) return 0;
if (a == 0)
{
if (c % b != 0) return 0;
y = c / b;
if (y >= y1 && y <= y2) return x2 - x1 + 1;
return 0;
}
if (b == 0)
{
if (c % a != 0) return 0;
x = c / a;
if (x >= x1 && x <= x2) return y2 - y1 + 1;
return 0;
}
/***********************特判***********************/
d = gcd (a, b);
if (c % d != 0) return 0;
a /= d, b /= d, c /= d;
Egcd (a, b, x, y);
x *= c;
x = (x % b + b) % b; //x的特解
s1 = cal (x1-x, b, b<0); //s1
e1 = cal (x2-x, b, b>0); //e1
y = (c - a*x) / b; //有了x,求对应的y
e2 = -cal (y1-y, a, a<0); //e2' = -s2
s2 = -cal (y2-y, a, a>0); //s2' = -e2
if (b < 0) s1 ^= e1, e1 ^= s1, s1 ^= e1; //b为负数,变号导致区间头尾互换
if (a < 0) s2 ^= e2, e2 ^= s2, s2 ^= e2; //同理
LL ans = min (e1, e2) - max (s1, s2) + 1;
if (ans < 0) ans = 0;
return ans;
}
int main()
{
LL x1, x2, y1, y2;
while (~scanf ("%lld%lld%lld", &a, &b, &c))
{
scanf ("%lld%lld%lld%lld", &x1, &x2, &y1, &y2);
printf ("%lld\n", solve (x1, x2, y1, y2));
}
return 0;
}
发表评论
-
HDU 4746 Mophues
2013-10-01 17:29 2976莫比乌斯函数完整定义的通俗表达: 1)莫比乌斯函数μ(n ... -
HDU 3221 Brute-force Algorithm
2013-05-04 13:31 1661/* * [题意] * 略 * [解题方法] ... -
UVA 10168 Summation of Four Primes
2013-02-14 21:48 1784/* * [题意] * 将一个数拆成四个素数的和, ... -
UVA 10139 Factovisors
2013-02-09 22:56 2116/* * [题意] * 判断n!是否能被m整除(n ... -
UVA 10104 Euclid Problem
2013-02-09 22:50 1477新手请进:扩展欧几里德入门 /* * ... -
UVA 10006 Carmichael Numbers
2013-02-08 08:27 2424/* * [题意] * 输入n,若满足如下两个条件 ... -
UVA 10110 Light, more light
2013-02-08 08:23 1402/* * [题意本质] * 输入n,如果n的约 ... -
【polya+Euler】HDU 2239 机器人的项链
2012-08-20 13:06 1423KIDx的解题报告 题目 ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1077KIDx的解题报告 题目链接:http://ac ... -
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2628KIDx的解题报告 题 ... -
【数论+容斥】POJ 1091 跳蚤
2012-05-17 13:11 3250KIDx的解题报告 题目链接:http://poj.o ... -
【数论法求一堆数的最小公倍数,结果高达几千位】LOJ 1024 Eid
2012-02-10 16:22 1779KIDx的解题报告 题意:求n个数的最小公倍数,结果很大 ... -
【预处理+卡特兰数+乘法逆元+二分查找】LOJ 1170
2012-01-14 12:57 2226KIDx 的解题报告 题目链接:http://ligh ... -
【快速幂取模】fzu 1752 A^B mod C
2011-11-25 23:32 3640KIDx 的解题报告 参考《算法艺术与信息学竞赛》: 题目 ... -
【高次幂取模的应用】HDU 3609 Up-up
2011-11-25 22:42 2250KIDx 的解题报告 题目很容易看懂:http://acm.h ... -
模线性方程组-非互质中国剩余定理 (更新于2012/5/18)
2011-11-18 19:03 4636KIDx 的解题报告 该专题必备知识:解模线性方程 http: ... -
【素数筛法小结】fzu 1607 + fzu 1753
2011-11-16 23:06 1668KIDx 的解题报告 http://acm.fzu.edu.c ... -
HDU 1410 PK武林盟主
2011-10-02 16:28 1100KIDx 的解题报告 题目链接: http://acm.h ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2548KIDx 的解题报告 http://acm.hdu.ed ... -
【提取素因子+积性函数】小明的密钥
2011-08-23 15:48 970http://acm.nyist.net/JudgeO ...
相关推荐
欧几里德算法和扩展欧几里德算法,经典算法系列
欧几里德算法和扩展欧几里德算法.doc
欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。
就是扩展欧几里德算法
扩展欧几里德定理
RSA扩展欧几里德算法算例,说明RSA密钥计算过程.
扩展欧几里德算法 欧几里德算法 代码 不可多得的资源
acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 很详细的讲解哦!
欧几里德算法和扩展欧几里德算法。用C和C++实现。.zip
扩展欧几里德问题,总结的课件,基本的内容都有了,由欧几里德引申到扩展欧几里德问题
实现扩展欧几里得算法的代码,很简单,能够成功运行。
个人初学C++,小试身手,供参考,网上有很多,我的是原创,但不是最好的
Matlab,扩展欧几里德算法,求模b条件下,a的乘法逆元,函数Eulid.m,直接调用传入参数就可以用,含参数使用注释。
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们 很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为 止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的...
扩展欧几里得算法求逆元
欧几里德算法 欧几里德算法 欧几里德算法 欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法
包含两个功能。 one 函数计算两个多项式 a(x) 和 b(x) 在 GF(2^m) 上... 另一个函数执行扩展的欧几里德算法,其中除了 a(x) 和 b(x) 的 gcd 之外,还计算了两个多项式 u(x) 和 v(x),使得 gcd = u(x)a(x) + v(x)b(x)。
欧几里德算法和扩展.doc
乘法逆元算法,扩展欧几里德,自己实现的,不过借鉴了网上的发达发达省份打发打发
介绍Pad6逼近的一般理论,通过引入扩展欧几里德算法给出对任何形式幂级数(n,m)阶Pade逼近的一种计算方法;还给出该方法求Pade逼近的一个应用实例.