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