文档章节

解二元一次不定方程的算法

m2012
 m2012
发布于 2012/05/14 19:35
字数 257
阅读 152
收藏 0

写下来,怕忘记。

假设二元一次方程的形式是 ax + by = c

先来简单的。假设a,b,c都是大于等于0的。假设d = gcd(a,b),那么c肯定可以表示为 c = nd,这个告诉我们,只要我们可以解出 ax + by = d 这个方程,然后两边乘以n,就可以得到 a(nx)+b(ny)=(nd) = c了。

注意到,ax + by = d 可以用扩展欧几里得算法搞定。所以,问题就搞定了。

然后看一下,如果允许a,b,c为负数的时候应该怎么做。
先把c弄成非负数,如果是c是负数,就把方程两边乘以-1吧。
然后,设A = abs(a), B = abs(b)
再定义个符号函数 s(x) = 1 if x >=0 else (-1)
那么,ax + by = c可以化为
A*s(a)*x + B*s(b)*y = c
也就是
A * ( s(a) * x ) + B ( s(b) * y ) = c
这个时候,A,B和c都是非负数,问题解决了!

© 著作权归作者所有

共有 人打赏支持
上一篇: 关于拆点法和DP
下一篇: sgu 230 - 拓扑排序
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
poj1061 - 同余方程,二元一次不定方程

以前不会解二元一次不定方程的时候不会做,现在会做了。 #include <cstdio> include <cassert> using namespace std; typedef int64 int64; void solveType1(int64 a, int64 b, int64 & x, i......

m2012
2012/05/24
0
0
Matlab--1

LINPACK : 软件包; 大矩阵 -- 三位空间和形象 -- 应用实例 一。 1.解 解 2.二元方程组的意义: 画出他们的直线:a:有解,有交点;b:无解,平行c:无穷多解:重合了 3,超定二元方程--近似解...

散人lin
2017/11/17
0
0
机器学习笔记-利用线性模型进行分类

利用线性模型进行二分类 线性模型 这一部分主要是为了证明为什么可以使用线性回归和逻辑斯蒂回归来做二元分类问题。 我们想要将已知的线性模型应用到二分类甚至是多分类的问题。我们已知的线...

robin_Xu_shuai
2017/08/16
0
0
文本分类又来了,用 Scikit-Learn 解决多类文本分类问题

雷锋网按:本文为雷锋字幕组编译的技术博客,原标题 Multi-Class Text Classification with Scikit-Learn,作者为 Susan Li 。 翻译 | 朱茵 整理 | 余杭 MY 在商业领域有很多文本分类的应用,...

雷锋字幕组
2018/07/25
0
0
第十章 Scala 容器基础(十九):把序列分解成子集(group by,partition等)

Problem 你想要基于一种算法或者规则,把一个序列切分为两个或者多个子集。 Solution 使用groupBy,partition,span,splitAt方法可以把一个集合切分成子集合。sliding和unzip方法也可以用来...

阿拉德大陆的魔法师
2016/04/14
433
0

没有更多内容

加载失败,请刷新页面

加载更多

“好”接口的设计与实现

一、好接口的特性 易读 易用,难于误用 功能独立 容易扩展 二、好接口设计的基本原则 只做并做好一件事 函数名自解释 不恰当的函数名,往往是不恰当设计的征兆 如果没做到上一点,就将函数分...

mskk
32分钟前
0
0
zabbix安装配置

环境 系统:centos7.5软件版本: mysql: 5.7 zabbix: 3.4.15内网: Port: 10051 IP: 192.168.2.71外网: Port: 34521 Domain: freefrp.cnAgent被动模式(默认) ...

亦漩
51分钟前
2
0
一看就能学会的H5视频推流方案

本文由云+社区发表 作者:周超 导语 随着直播平台爆发式增长,直播平台从 PC 端转战移动端,紧跟着直播的潮流,自己学习实现了一套简单的 H5 视频推流的解决方案,下面就给小伙伴们分享一下自...

腾讯云加社区
54分钟前
4
0
Spring Boot 2.X优雅停止

本文章介绍了正常关闭Spring Boot 应用程序的过程。许多开发人员和架构师总是讨论SpringBoot的应用设计、流量负载、框架和应用模式,但很少有人讨论关闭阶段。生命周期意识可以说一个真正资深...

WUBAOQUAN
今天
6
0
Linux Redis 高可用之主从复制

Redis主从复制简介 和MySQL主从复制的原因一样,Redis虽然读取写入的速度都特别快,但是也会产生读压力特别大的情况。为了分担读压力,Redis支持主从复制,Redis的主从结构可以采用一主多从或...

我最喜欢三大框架
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部