刚学习的扩展欧几里得算法,刷个水题
求解 线性不定方程 和 模线性方程
求方程 ax+by=c 或 ax≡c (mod b) 的整数解
1、ax+by=gcd(a,b)的一个整数解:
<span style="font-size:14px;">void ex_gcd(int a,int b,int &d,int &x,int &y)//扩展欧几里得算法
{
if(!b){d=a;x=1;y=0;}
else {ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}
}</span>
2、ax+by=c的全部整数解:
方程两边同一时候乘以g/c(g为a,b的最大公约数)。则原方程为 g *a/c *x+g*b/c*y=g
则g*x/c=x0,g*y/c=y0 ( x0,y0为 方程ax+by=gcd(a,b)的一个特解)
所以原方程的一个特解x=x0*c/g,y=y0*c/g
求通解的过程省略。
。。
最后通解为 (x+kb1,y-ka1) b1=b/g,a1=a/g。
3、ax≡c (mod b)方程的全部整数解:
ax和c关于模b同余。则(ax-c)是b的整数倍。设倍数为y,则原方程等价于 ax-c=by,移项得 ax-by=c,转变为求解ax+by=c的形式
假设两个数的最大公约数为1。则两个数互质
题目分析:
给定 a b k找到满足ax+by=k 的令|x|+|y|最小(等时令a|x|+b|y|最小)最好还是a 〉b
先用扩展欧几里得算法求出 一组解 x0。y0,通解能够表示为x=x0+b/d *t y=y0-a/d *t
|x|+|y|=|x0+b/d *t |+|y0-a/d *t| 这个关于t的函数的最小值在 t = y0*d/a 附近的两整点里取。故直接验证这两点就可以。
由于 设a>b之后
|x0+b/d *t| 单调递增,|y0-a/d*t| 先递减再递增。
因斜率a/d>b/d。所以总的|x0+b/d *t |+|y0-a/d *t| 先递减再递增,使y0-a/d*t0=0 的t0附近有最小值。
//转载
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x0,z1,a1,b1;
void ex_gcd(int a,int b,int &d,int &x,int &y)
{
if(!b){d=a;x=1;y=0;}
else {ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int calx(int k)
{
return abs(x0+k*b1);
}
int caly(int k)
{
return abs(z1-k*a1);
}
int main()
{
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c)&&(a||b||c)){
int flag=1;
if(a<b) {flag=0;swap(a,b);}
int d,x,y,k,k1,k2;
ex_gcd(a,b,d,x,y);
x0=x*(c/d),z1=y*(c/d);
a1=a/d,b1=b/d,k1=z1/a1;
if(k1*a1-z1>=0) k1--;
k2=k1+1;
if(calx(k1)+caly(k1)>calx(k2)+caly(k2)) k=k2;
else if(calx(k1)+caly(k1)<calx(k2)+caly(k2)) k=k1;
else{
if(calx(k1)*a+caly(k1)*b>calx(k2)*a+caly(k2)*b) k=k2;
else k=k1;
}
int ansx=calx(k);
int ansy=caly(k);
if(!flag){
printf("%d %d\n",ansy,ansx);
}
else printf("%d %d\n",ansx,ansy);
} return 0;
}
POJ2142——The Balance的更多相关文章
-
poj2142 The Balance
poj2142 The Balance exgcd 应分为2种情况分类讨论 显然我们可以列出方程 ax-by=±d 当方程右侧为-d时,可得 by-ax=d 于是我们就得到了2个方程: ax-by=d ...
-
[暑假集训--数论]poj2142 The Balance
Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. F ...
-
POJ2142 The Balance (扩展欧几里德)
本文为博主原创文章,欢迎转载,请注明出处 www.cnblogs.com/yangyaojia The Balance 题目大意 你有一个天平(天平左右两边都可以放砝码)与重量为a,b(1<= ...
-
POJ-2142 The Balance 扩展欧几里德(+绝对值和最小化)
题目链接:https://cn.vjudge.net/problem/POJ-2142 题意 自己看题吧,懒得解释 思路 第一部分就是扩展欧几里德 接下来是根据 $ x=x_0+kb', y=y_0- ...
-
poj2142 The Balance 扩展欧几里德的应用 稍微还是有点难度的
题目意思一开始没理解,原来是 给你重为a,b,的砝码 求测出 重量为d的砝码,a,b砝码可以无限量使用 开始时我列出来三个方程 : a*x+b*y=d; a*x-b*y=d; b*y-ax=d; 傻眼 ...
-
POJ2142:The Balance (欧几里得+不等式)
Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. F ...
-
The Balance(poj2142)
The Balance Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 5452 Accepted: 2380 Descr ...
-
POJ2142:The Balance——题解
http://poj.org/problem?id=2142 题目大意:有一天平和两种数量无限的砝码(重为a和b),天平左右都可以放砝码,称质量为c的物品,要求:放置的砝码数量尽量少:当砝码数量相同时 ...
-
Sample a balance dataset from imbalance dataset and save it(从不平衡数据中抽取平衡数据,并保存)
有时我们在实际分类数据挖掘中经常会遇到,类别样本很不均衡,直接使用这种不均衡数据会影响一些模型的分类效果,如logistic regression,SVM等,一种解决办法就是对数据进行均衡采样,这里就 ...
随机推荐
-
消除类游戏(js版)
最近一直在玩一款消灭星星的消除类游戏,周末无聊就用js也写了一遍,感觉玩比写还困难一直玩不到10000分.废话不多说直接上源码. 效果图(ps 页面有点难看木有美工) 代码总共456行,未经过严格测试 ...
-
spring来了-04-AOP
概述 aspect object programming 面向切面编程 功能:可以实现“业务代码”与“关注点代码”分离 关注点代码:就是指重复执行的代码 业务代码:核心的业务功能 运行期间,执行核心业 ...
-
Zend Server更新至6.2版本——虚拟主机全方位管理
Zend Server自从发布6.0以来,并支持云服务,成为很多PHP程序所选择的Web服务器. Zend Server 6.2版本从更新内容来看,解决了Web服务器与虚拟主机之间的协同管理.并在细节 ...
-
编写一个简单的Web Server
编写一个简单的Web Server其实是轻而易举的.如果我们只是想托管一些HTML页面,我们可以这么实现: 在VS2013中创建一个C# 控制台程序 编写一个字符串扩展方法类,主要用于在URL中截取文 ...
-
freemark标签从后台接过来数据Boolean在前台还是Boolean输出(四)
FREEMARK标签中输出BOOLEAN值 private boolean showHeader=true; public boolean getShowHeader(){ return this.s ...
-
windows下通过压缩包安装MySQL
一.下载压缩包 二.解压缩后存放在该路径下 三.配置环境变量 将D:\Program Files\mysql-8.0.11-winx64\bin添加到用户PATH变量或系统PATH变量中 ...
-
如何在linux下检测内存泄漏(转)
本文转自:http://www.ibm.com/developerworks/cn/linux/l-mleak/ 本文针对 linux 下的 C++ 程序的内存泄漏的检测方法及其实现进行探讨.其中包括 ...
-
读DataSnap源代码(六)
具体分析一下DataSanp App与Rest, WebBroker App的不同,先看TDSHTTPService. **************************************** ...
-
通读cheerio API
所谓工欲善其事,必先利其器,所以通读了cheerio的API,顺便翻译了一遍,有些地方因为知道的比较少,不知道什么意思,保留了英文,希望各位不吝告诉我,然后一起把这个翻译完成. ###cheerio ...
-
SQL SERVER常用的统计用法
--查询各个状态下总数SET statistics time on Go SELECT END ) AS Q1, END ) AS Q2, END ) AS Q3, END ) AS Q4, END ...