很不错的题,加深了我对exgcd的理解

(以前我认为做题就是搜索、dp...原来数学也很重要)

理解了几个小时,终于明白了。但我什么都不打算写。

看代码吧:

#include<iostream>
using namespace std; int exgcd(int a,int b,int& x,int&y){//扩展欧几里得
if(b==){
x=; y=;
return a;
}
int x2,y2;
int d=exgcd(b,a%b,x2,y2);
x=y2; y=x2-(a/b)*y2;
return d;
} int main(){
int T; cin>>T;
while(T--){
int a,b,c,lx,hx,ly,hy;
cin>>a>>b>>c>>lx>>hx>>ly>>hy;
c=-c;
if(lx>hx||ly>hy||(a==&&b==&&c!=)){cout<<<<endl; continue;}
if(a==||b==){
long long num_x,num_y;
if(a==)num_x=hx-lx+;
else if(c%a==&&(c/a)<=hx&&(c/a)>=lx)num_x=;
else num_x=;
if(b==)num_y=hy-ly+;
else if(c%b==&&(c/b)<=hy&&(c/b)>=ly)num_y=;
else num_y=;
cout<<num_x*num_y<<endl;
continue;
}
int x,y;
int d=exgcd(a,b,x,y);
if(c%d!=){cout<<<<endl; continue;}
int k=c/d;
x*=k; y*=k;
a/=d; b/=d;
// cout<<x<<' '<<y<<endl;
if(x<lx){
while(x<lx){
x+=b;
y-=a;
}
}
else{
while(x>=lx){
x-=b;
y+=a;
}
x+=b; y-=a;
} long long ans=;
while(x<=hx){
if(y<=hy&&y>=ly){
ans++;
// cout<<x<<' '<<y<<endl;
}
x+=b;
y-=a;
}
cout<<ans<<endl;
}
}

最新文章

  1. svn/git的diff、patch
  2. 【iCore3 双核心板_FPGA】例程六:计数器实验——计数器使用
  3. 【小白入门向】tarjan算法+codevs1332上白泽慧音 题解报告
  4. Visual Studio 2015 社区版.专业版.企业版[含安装密钥Pro&amp;Ent]
  5. .net中自定义过滤器对Response内容进行处理
  6. 解决: Can’t connect to local MySQL server through socket /var/lib/mysql/mysql.sock
  7. php中count获取多维数组长度的方法
  8. 第十四章:高级I/O
  9. Python 简单爬虫
  10. 【自动化测试】Selenium处理富文本框
  11. memcachedd基础
  12. bzoj 1025 [SCOI2009]游戏(置换群,DP)
  13. jQuery,javascript获得网页的高度和宽度
  14. 11i - 12 How To Set Email Style Preference For All Users At Once?
  15. 关于Visio Studio 2012使用Nuget获取Sqlite驱动包报错:“System.Data.SQLite.EF6”的架构版本与 NuGet 的版本 2.0.30625.9003 不兼容
  16. 通用后台管理系统UI-AdminLTE:构造动态菜单栏
  17. WCF服务寄宿到IIS
  18. javascript之BOM浏览器对象模型引入
  19. Tkinter小技巧:如何为窗口右上角的‘x’添加一个自定义的响应函数
  20. element 给table的个别表格框添加样式 ---重构里面的组件

热门文章

  1. web.py尝试性学习!
  2. [Flutter] Windows平台Flutter开发环境搭建(Andorid Studio)
  3. C_point指针
  4. python入门-用户输入
  5. MVC,MVP 和 MVVM 模式如何选择?
  6. 数据结构之线索二叉树——C语言实现
  7. Java的Guava
  8. delphi IDE RAD 丢失的快捷键 Ctrl+Shift+F
  9. input文本框 放上图片img 通过padding relative和absolute 的实现
  10. ABAP-Keyword Documentation