嗯...
题目链接:http://poj.org/problem?id=2142
AC代码:
#include<cstdio>
#include<iostream> using namespace std; inline int _abs(int x){
if(x < ) return -x;
return x;
} inline void exgcd(int a, int b, int &g, int &x, int &y){
if(!b) { g = a; x = ; y = ;}
else { exgcd(b, a % b, g, y, x); y -= x * (a / b);}
} inline void work(int a, int b, int c, int &g, int &x, int &y){
exgcd(a, b, g, x, y);
x *= c / g;
int t = b / g;
x = (x % t + t) % t;
y = _abs((a * x - c) / b);
} int main(){
int a, b, c, x1, g, y1, x2, y2;
while(~scanf("%d%d%d", &a, &b, &c)){
if(!a && !b && !c) break;
work(a, b, c, g, x1, y1);
work(b, a, c, g, x2, y2);
if(x1 + y1 < x2 + y2) printf("%d %d\n", x1, y1);
else printf("%d %d\n", y2, x2);
}
return ;
}
AC代码
POJ 2142 The Balance(exgcd)的更多相关文章
-
POJ - 2142 The Balance(扩展欧几里得求解不定方程)
d.用2种砝码,质量分别为a和b,称出质量为d的物品.求所用的砝码总数量最小(x+y最小),并且总质量最小(ax+by最小). s.扩展欧几里得求解不定方程. 设ax+by=d. 题意说不定方程一定有 ...
-
POJ 2142 The Balance (解不定方程,找最小值)
这题实际解不定方程:ax+by=c只不过题目要求我们解出的x和y 满足|x|+|y|最小,当|x|+|y|相同时,满足|ax|+|by|最小.首先用扩展欧几里德,很容易得出x和y的解.一开始不妨令a& ...
-
【题解】POJ 2115 C Looooops (Exgcd)
POJ 2115:http://poj.org/problem?id=2115 思路 设循环T次 则要满足A≡(B+CT)(mod 2k) 可得 A=B+CT+m*2k 移项得C*T+2k*m=B-A ...
-
POJ 2115 C Looooops(Exgcd)
[题目链接] http://poj.org/problem?id=2115 [题目大意] 求for (variable = A; variable != B; variable += C)的循环次数, ...
-
POJ.2142 The Balance (拓展欧几里得)
POJ.2142 The Balance (拓展欧几里得) 题意分析 现有2种质量为a克与b克的砝码,求最少 分别用多少个(同时总质量也最小)砝码,使得能称出c克的物品. 设两种砝码分别有x个与y个, ...
-
POJ 3669 Meteor Shower(流星雨)
POJ 3669 Meteor Shower(流星雨) Time Limit: 1000MS Memory Limit: 65536K Description 题目描述 Bessie hears ...
-
POJ 3253 Fence Repair (优先队列)
POJ 3253 Fence Repair (优先队列) Farmer John wants to repair a small length of the fence around the past ...
-
【POJ 3071】 Football(DP)
[POJ 3071] Football(DP) Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4350 Accepted ...
-
Poj 3613 Cow Relays (图论)
Poj 3613 Cow Relays (图论) 题目大意 给出一个无向图,T条边,给出N,S,E,求S到E经过N条边的最短路径长度 理论上讲就是给了有n条边限制的最短路 solution 最一开始想 ...
随机推荐
-
Python 函数嵌套
def mumber(a): def add(b): return a*b return add if __name__=="__main__& ...
-
callback 转换到 promise
最近项目迭代,从express到koa,面对callback,想偷懒,就想到了Proxy对象 new Proxy(docker,{ get : function (obj,name) { return ...
-
Swift3.0语言教程组合字符串
Swift3.0语言教程组合字符串 Swift3.0语言教程组合字符串,当开发者想要将已经存在的字符串进行组合,形成一个新的字符串,可以使用NSString中的两个方法,分别为appending(_: ...
-
Delphi流的操作 转
一.流的概念 流简单说是建立在面向对象基础上的一种抽象的处理数据的工具,它定义了一些处理数据的基本操作,如读取数据,写入数据等,程序员只需掌握对流进行操作,而不用关心流的另一头数据的真正流向.其实,流 ...
-
python中的 json 模块使用
(1)python 中生成 json 字符串: import json data = dict(ret=0, msg="Welcome, Login success!") json ...
-
每天一个linux命令(54)--watch命令
watch是一个非常实用的命,基本所有的Linux发行版都带有这个小工具,如同名字一样,watch可以帮你监测一个命令的运行结果,省的你一遍遍的手动运行,在Linux下,watch是周期性的执行下个程 ...
-
[BZOJ1552] [Cerc2007] robotic sort (splay)
Description Input 输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000.第二行为N个用空格隔开的正整数,表示N个物品最初排列的编号. Output ...
-
后端分布式系列:分布式存储-HDFS DataNode 设计实现解析
前文分析了 NameNode,本文进一步解析 DataNode 的设计和实现要点. 文件存储 DataNode 正如其名是负责存储文件数据的节点.HDFS 中文件的存储方式是将文件按块(block)切 ...
-
OJ题:将一个数倒置输出
题目描述: 输入一个数,假如num = 12345 , 输出 54321,以此类推. 代码实现: ) ; }
-
Python日期的加减等操作
1. 日期输出格式化 所有日期.时间的api都在datetime模块内. 1. datetime => string now = datetime.datetime.now() now.strf ...