荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: Version (Who makes history and why), 信区: Program
标 题: [合集]一个关于分数的题目 birdf (转寄)[转载]
发信站: 荔园晨风BBS站 (Sun Apr 20 23:12:11 2003), 站内信件
【 以下文字转载自 Version 的信箱 】
【 原文由 pcAngel@bbs.pku.edu.cn 所发表 】
发信人: readchild (Bayes), 信区: ACM_ICPC
标 题: 征解题1
发信站: 北大未名站 (2002年09月26日12:22:25 星期四), 转信
给出若干个不超过20地正整数，给出一个分数
要求从中选出若干个数的乘积作为分母，若干个数的乘积作为分子，，可以重用
判断能否得到所要求的数
--
.:::::::::::::::::::::: |\| | | |\ / \ /_| :::::::::::::.
::::::::::::::::::::::. \ | | /|'/ / | \ /_ | :::::::::::::::
::::::::::::::' ,_ '::: `\ \/|/ / /`.: \ /__/ ::::::::::::::::
::::::::::::: /\/`'. ':. `\ `./.'/\ : /.--' .:::::::::::::::::
::::::::::::: |_\ / \ ::. '. ,/|\/| // '''''::::::::::::::::
::::::::::::: | _\ / | .:: | | \ \/// .""'-. ::::::::::::::
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.110.253]
发信人: victorshi (孤鸿影), 信区: ACM_ICPC
标 题: Re: 征解题1
发信站: 北大未名站 (2002年09月26日12:58:21 星期四), 转信
将分数化为既约分数，如下形式：
a(1)^f(1)*a(2)^f(2)……
-----------------------
a(1)^e(1)*a(2)^e(2)……
其中 a(1)=2，a(2)=3……
a(i)为第i个质数
设每个给出的正整数如下：
n(i) = a(1)^p(i,1)*a(2)^p(i,2)……
a(i)定义同上
解方程组：
sigma{[x(i)-y(i)]*p(i,j)} = f(j)-e(j)
其中x(i)为分子上各数的系数
y(i)为分母上各数的系数
(1)有解,任意解皆为原题的解
(2)无解,原题无解
【 在 readchild (Bayes) 的大作中提到: 】
: 给出若干个不超过20地正整数，给出一个分数
: 要求从中选出若干个数的乘积作为分母，若干个数的乘积作为分子，，可以重用
: 判断能否得到所要求的数
--
江南好
风景旧曾谙
日出江花红胜火
春来江水绿如蓝
能不忆江南
※ 修改:·victorshi 于 09月26日12:59:41 修改本文·[FROM: 166.111.136.45]
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 166.111.136.45]
发信人: readchild (Bayes), 信区: ACM_ICPC
标 题: Re: 征解题1
发信站: 北大未名站 (2002年09月26日13:07:43 星期四), 转信
但是这个关于整数的多元不定方程组有什么容易实现的解法么？
【 在 victorshi (孤鸿影) 的大作中提到: 】
: 将分数化为既约分数，如下形式：
: a(1)^f(1)*a(2)^f(2)……
: -----------------------
: a(1)^e(1)*a(2)^e(2)……
: 其中 a(1)=2，a(2)=3……
: a(i)为第i个质数
: 设每个给出的正整数如下：
: n(i) = a(1)^p(i,1)*a(2)^p(i,2)……
: a(i)定义同上
: 解方程组：
: ...........................
--
':::::::::: | | ::::::::::'
':::::::: | |} ::::::::'
':::::: | | ::::::'
':::::. |/ ::::::'
':::.....:::::'
':::::::::'
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.110.253]
发信人: victorshi (孤鸿影), 信区: ACM_ICPC
标 题: Re: 征解题1
发信站: 北大未名站 (2002年09月26日13:13:57 星期四), 转信
只要有解,必然有整数解
(对于任一解,必有对应的整数解)
理由是对于任一解,根据代入与消元的法则,必然是有理数解
x(i)=p(i)/q(i)
y(i)=s(i)/t(i)
令
k=[q(i),t(i)](最小公倍数)
x'(i)=k*x(i)
y'(i)=k*y(i)
【 在 readchild (Bayes) 的大作中提到: 】
: 但是这个关于整数的多元不定方程组有什么容易实现的解法么？
--
江南好
风景旧曾谙
日出江花红胜火
春来江水绿如蓝
能不忆江南
※ 修改:·victorshi 于 09月26日13:17:58 修改本文·[FROM: 166.111.136.45]
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 166.111.136.45]
发信人: readchild (Bayes), 信区: ACM_ICPC
标 题: Re: 征解题1
发信站: 北大未名站 (2002年09月26日13:20:36 星期四), 转信
高斯定理确实保证了这一点
但问题是方程怎么去解，未知数多余方程个数阿
【 在 victorshi (孤鸿影) 的大作中提到: 】
: 只要有解,必然有整数解
: (对于任一解,必有对应的整数解)
: 理由是对于任一解,根据代入与消元的法则,必然是有理数解
: x(i)=p(i)/q(i)
: y(i)=s(i)/t(i)
: 令
: k=[q(i),t(i)](最小公倍数)
: x'(i)=k*x(i)
: y'(i)=k*y(i)
--
.::::::::::::::::::::::::::::::::::::::::::::.
.:::::::::::::::::::'.-=.-~, ':::::::::::::::::::.
.:::::::::::::::::::' /{,_;--'},'::::::::::::::::::::.
.:::::::::::::::::::: | .=~`|//| :::::::::::::::::::::.
.::::::::::::::::::::: | / ; \ | :::' __, '::::::::::::.
.:::::::::::::::::::::' || | | | :' .' \/\ ::::::::::::.
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.110.253]
发信人: victorshi (孤鸿影), 信区: ACM_ICPC
标 题: Re: 征解题1
发信站: 北大未名站 (2002年09月26日13:25:12 星期四), 转信
先消元,使得各变量线性无关
如果此时未知数个数>=方程个数,任意代入即可
(好像线性代数书里说得还是比较清楚的)
另外要说明一种情况:
若消元后有形如
x=b (b<0)
则无解
当然如果要较真的话,可以加上条件
x(i)>=0
y(i)>=0
解出不等式组的解空间,在解空间中取任意有理值代入
【 在 readchild (Bayes) 的大作中提到: 】
: 高斯定理确实保证了这一点
: 但问题是方程怎么去解，未知数多余方程个数阿
--
天下事了犹未了，何不以不了了之
※ 修改:·victorshi 于 09月26日13:29:24 修改本文·[FROM: 166.111.136.45]
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 166.111.136.45]
发信人: readchild (Bayes), 信区: ACM_ICPC
标 题: Re: 征解题1
发信站: 北大未名站 (2002年09月26日13:31:49 星期四), 转信
理论上是没有问题了
thx
【 在 victorshi (孤鸿影) 的大作中提到: 】
: 先消元,使得各变量线性无关
: 如果此时未知数个数>=方程个数,任意代入即可
: (好像线性代数书里说得还是比较清楚的)
: 另外要说明一种情况:
: 若消元后有形如
: x=b (b<0)
: 则无解
: 当然如果要较真的话,可以加上条件
: x(i)>=0
: y(i)>=0
: ...........................
--
:::::::::::::: \__\ / .: .'/| | `)`/__//_/_/_\ ::::::::::::
':::::::::::::: '--.\ : /\/_| |} /.---. \ \ \ / ::::::::::::'
'::::::::::::'' \\|\/_/| | //` . `'...-' ::::::::::::'
:::::::::: .-""'. \\\//{| |// .:::::....::::::::::::::'
'::::::: /_\_\_\\__\`(` | '/ ::::::::::::::::::::::::'
':::::: \ / / / .---.\ | | :::::::::::::::::::::::'
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.110.253]
发信人: hawking (走了), 信区: ACM_ICPC
标 题: Re: 征解题1
发信站: 北大未名站 (2002年09月26日15:57:23 星期四), 转信
何必用x（i）和y（i）
两个？只用一个，然后求整数解不就可以了吗
还有，这两个应该是分子分母上各个数的幂吧，而不是系数哦
【 在 victorshi (孤鸿影) 的大作中提到: 】
: 先消元,使得各变量线性无关
: 如果此时未知数个数>=方程个数,任意代入即可
: (好像线性代数书里说得还是比较清楚的)
: 另外要说明一种情况:
: 若消元后有形如
: x=b (b<0)
: 则无解
: 当然如果要较真的话,可以加上条件
: x(i)>=0
: y(i)>=0
: ...........................
--
这些日子，是上天的恩惠，不能再浪费了
◎◎一颗破碎的心◎◎
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.52.129]
发信人: victorshi (孤鸿影), 信区: ACM_ICPC
标 题: Re: 征解题1
发信站: 北大未名站 (2002年09月26日17:26:59 星期四), 转信
【 在 hawking (走了) 的大作中提到: 】
: 何必用x（i）和y（i）
看得清楚
: 两个？只用一个，然后求整数解不就可以了吗
: 还有，这两个应该是分子分母上各个数的幂吧，而不是系数哦
这个我表达得不太清楚
--
天下事了犹未了，何不以不了了之
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 166.111.136.45]
--
※ 转寄:·北大未名站 bbs.pku.edu.cn·[FROM: 210.39.3.50]
--
※ 转载:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.1.50]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店