zgg___ 发表于 2011-12-13 12:57:08

请教关于线性不定方程非负整数解计数的问题

给定a1、a2、……、an（它们都是大于1的实数），求不定方程x1/a1+x2/a2+……+xn/an<=1的非负整数解的组数。

求一种算法，在n<10^5、a<100的规模下能够解决问题。

wayne 发表于 2011-12-13 13:50:11

把x1/a1+x2/a2+……+xn/an<=1 转化成整数系数的形式b1*x1+b2*x2+...+bn*xn <=a1*a2*....an

倘若我们解方程b1*x1+b2*x2+...+bn*xn =a1*a2*....an得到 x1=c1,x2=c2, ... , xn=cn .
那么原不等式解的个数就等于(c1+1)(c2+1)....(cn+1) 了

wayne 发表于 2011-12-13 13:57:29

哦，不对，方程b1*x1+b2*x2+...+bn*xn =a1*a2*....an   的解不唯一

那就这样，分别对 T属于 【0，a1*a2*....an】，解方程 b1*x1+b2*x2+...+bn*xn =T 的个数。然后相加

wayne 发表于 2011-12-13 14:01:51

呃，规模太大了吧

wayne 发表于 2011-12-16 18:06:47

a1、a2、……、an都是正整数就好说话了

求方程x1/a1+x2/a2+……+xn/an =1的非负整数解的组数T。
于是原不等式的解的个数就是(1+a1)(1+a2)...(1+an) +T-2 的一半。

zgg___ 发表于 2011-12-16 21:32:08

a1、a2、……、an都是正整数就好说话了

求方程x1/a1+x2/a2+……+xn/an =1的非负整数解的组数T。
于是原不等式的解的个数就是(1+a1)(1+a2)...(1+an) +T-2 的一半。
wayne 发表于 2011-12-16 18:06 http://bbs.emath.ac.cn/images/common/back.gif

正是这样的呢:b: ，如果它们都是正整数，题目可能就好算些了，因为所谓pick定理以及“Ehrhart polynomial”的东东就可以用上了呢。赫赫。

wayne 发表于 2011-12-16 22:02:11

6# zgg___
:L
俺仅仅根据n=2的情形，利用对称性拼凑出来的
好像不是很稳妥

我待会用软件验证一下

wayne 发表于 2011-12-16 22:13:26

经验证，我那个计数的推广是错误的，好像仅仅对n=2成立。
pick定理以及 "Ehrhart polynomial"才是正点。

罪过罪过。。。

shshsh_0510 发表于 2011-12-19 10:18:11

pslq算法

zgg___ 发表于 2011-12-19 10:58:21

pslq算法
shshsh_0510 发表于 2011-12-19 10:18 http://bbs.emath.ac.cn/images/common/back.gif

对于PSLQ、LLL啥的稍稍有一点点了解。知道貌似这些东东可以用来求a1*x1+a2*x2+……+an*xn==1（其中an为已知实数，xn为要求解的未知正整数）的近似解（即==是约等于），但是不明白如何运用到本题中呢。请具体说说呢，赫赫。
页: [1]
查看完整版本: 请教关于线性不定方程非负整数解计数的问题