终于a了,这题还是比较麻烦的~wa的原因是没有考虑相除后是取它的上底还是下底。。。
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a) for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a) for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a) scanf(in64,&a)
#define SS(a) scanf("%d",&a)
#define LL(a) ((a)<<1)
#define RR(a) (((a)<<1)+1)
#define SZ(a) ((int)a.size())
#define PP(n,m,a) puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb push_back
#define CL(Q) while(!Q.empty())Q.pop()
#define MM(name,what) memset(name,what,sizeof(name))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-10;
const double pi = acos(-1.0);
i64 gcd(i64 _a, i64 _b)
{
if (!_a || !_b)
{
return max(_a, _b);
}
i64 _t;
while (_t = _a % _b)
{
_a = _b;
_b = _t;
}
return _b;
};
i64 ext_gcd (i64 _a, i64 _b, i64 &_x, i64 &_y)
{
if (!_b)
{
_x = 1;
_y = 0;
return _a;
}
i64 _d = ext_gcd (_b, _a % _b, _x, _y);
i64 _t = _x;
_x = _y;
_y = _t - _a / _b * _y;
return _d;
}
i64 exmod (i64 _a, i64 _p)
{
i64 _ans, _y;
ext_gcd (_a, _p, _ans, _y);
_ans < 0 ? _ans += _p : 0;
return _ans;
}
i64 a,b,c,x1,x2,y11,y22;
i64 gab;
i64 x,y;
i64 ans;
i64 findx(i64 q1,i64 q2,i64 w1,i64 w2)
{
if(q1>q2)
{
swap(q1,q2);
}
if(w1>w2)
{
swap(w1,w2);
}
if(q1 > w2 || q2 < w1)
{
return 0;
}
else if(q1<=w1 && w2<=q2)
{
return w2-w1+1;
}
else if(q1>=w1 &&q1<=w2)
{
if(q2<=w2)
{
return q2-q1+1;
}
else
{
return w2 - q1+1;
}
}
else if(q2>=w1 && q2 <= w2)
{
if(q1>=w1)
{
return q2 - q1 +1;
}
else
{
return q2 - w1 + 1;
}
}
}
int main()
{
i64 temp;
while(cin>>a>>b>>c)
{
cin>>x1>>x2;
cin>>y11>>y22;
if(a==0 && b==0)
{
if(c==0)
{
temp = (x2-x1+1)*(y22-y11+1);
cout<<temp<<endl;
continue;
}
else
{
cout<<"0"<<endl;
continue;
}
}
else if(a==0)
{
if(c%b==0)
{
temp = -c/b;
if(temp<=y22 && temp >= y11)
{
temp = x2-x1+1;
cout<<temp<<endl;
continue;
}
}
else
{
cout<<"0"<<endl;
continue;
}
}
else if(b==0)
{
if(c%a==0)
{
temp = -c/a;
if(temp <= x2 && temp >= x1)
{
temp = y22 - y11 +1;
cout<<temp<<endl;
continue;
}
}
else
{
cout<<"0"<<endl;
continue;
}
}
else
{
i64 t1,t2;
if(c>0)
{
c =- c;
a = -a;
b = -b;
}
c = -c;
if(a<0)
{
a = -a;
x1=-x1;
x2=-x2;
if(x1>x2)
swap(x1,x2);
}
if(b<0)
{
b=-b;
y11=-y11;
y22=-y22;
if(y11>y22)
swap(y11,y22);
}
gab = gcd(a,b);
a /= gab;
b /= gab;
if(c%gab!=0)
{
cout<<"0"<<endl;
continue;
}
x = exmod(a,b);
x *= c;
x %= b;
y = (c-a*x)/b;
i64 lix,rix;
i64 liy,riy;
lix = (x1-x)/b;
if(x1-x > 0 && (x1-x)%b!=0 )
{
lix ++;
}
rix = (x2-x)/b;
if(x2-x<0 && (x2-x)%b!=0)
{
rix--;
}
liy = (y-y22)/a;
if( y - y22 >0 && (y-y22)%a!=0)
{
liy++;
}
riy = (y-y11)/a;
if(y-y11<0 && (y-y11)%a != 0 )
{
riy--;
}
cout<<findx(lix,rix,liy,riy)<<endl;
}
}
return 0;
}
分享到:
相关推荐
SGU推荐题目分类,适合初次使用sgu的编程爱好者使用!
SGU 390 AC源码,数位统计的难题
SGU 385,我写的程序,一道DP题,跟概率有关
SGU题库整合 Volume (200 - 299) pdf版
辛苦整理所得,分略多,绝对值得,sgu完整题库(530个网页,还有试题难度排序)。lnddszp[at]gmail[dot]com
SGU离线题库(2015-6-8整理),图片可以显示。。
sgu oj上的 101-121 的AC代码
SGU-801综合通讯接入装置使用说明书
SGU 103AC 代码 质量有保证!
SGU 333 集训队AC程序,秒过,CPP
sgu ##这是一个将我的 sol 问题存储到 acm.sgu.ru 的存储库
SGU题库 Volume (100-199) pdf整合版
ID 标题 交流电 A + B 18881 互质 7697 第3分部 6906 总和 6185 日历 4336 画线 4159 987654321问题 4014 肉饼 3998 几乎素数 3845 a ^ b-b ^ a 3673 骨牌 3621 花小店 ...106 等式 1884
pku sgu 经典图论题解答, 多种方法解答经典图论题, 附源代码
sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 ...
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
下载调度程序,用于低带宽环境。 全天扩展下载量
HJVXJVHSKVH JHDK JH DFKSDYFS DVJDSVXCVXCVZXCVZXCV
“#babylonjs-sgu”
SGU-用于搜索github用户的输入表单- 描述 您可以通过输入一些文本来找到github用户。 然后,您将拥有一个用户名和用户图标。 仅显示搜索关键字和用户名之间的数据。 库版本 下一个v10.0.7 Reactv17.0.1 react-dom ...