免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数论] 不定方程

??????.png
2018-3-22 14:03
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 zhcosin 于 2018-3-22 14:39 编辑

回复 1# APPSYZY
在编程领域,判断一个算法的优劣,有时间复杂度和空间复杂度两个指标,分别指示随着问题规模的增长,算法所需要的时间开销和内存开销的增长阶。

在你这个问题中,问题的规模自然是 $x^2+y^2=n$ 右边的 $n$,所以只要考查算法的两个复杂度随着 $n$ 的增长是怎样一个增长态势。

至于空间复杂度嘛,显然整个过程中只需要存储$(x,y)$的当前值就行了,所以内存使用量是常量级别,即空间复杂度是 $O(1)$.

再来看时间复杂度,通常拿算法中的最基本操作所需要执行的次数来衡量,在这里,自然是枚举的次数了。对 $x^2+y^2=n$ 来说, $x$需要从 1 取到 $[\sqrt{n}]$,然后判断 $n-x^2$是否是平方数即可,所以需要的枚举次数就是 $[\sqrt{n}]$,所以这个算法的时间复杂度是 $O(\sqrt{n})$.

而对于 $x^2+y^2+z^2=n$ 方程来说,$x$ 的范围仍然是 1到$[\sqrt{n}]$,而对$x$的每一个取值,需要解方程$y^2+z^2=n-x^2$,所需要的枚举次数是$[\sqrt{n-x^2}]$,所以总共需要的枚举次数是
\[ \sum_{k=1}^{[\sqrt{n}]} [\sqrt{n-k^2}]  \]
取整并不影响它的增长阶,所以这个时间复杂度是
\[ \sum_{1 \leqslant k^2 \leqslant n} \sqrt{n-k^2} \]
看能不能找个简洁的式子与它同阶.

TOP

回复 1# APPSYZY

不会编程,但是觉得这样算可能不是最快的。如果能把2000分解因数,可以得到$2000=2^4 \cdot 5^3$,然后可以写成下面这样:$2000=2 \cdot 1000=(1^2+1^2)\cdot1000$,同样$1000=(1^2+1^2)\cdot500,500=(1^2+1^2)\cdot250$,最后$250=(1^2+1^2)\cdot125=(1^2+1^2)(5^2+10^2)=5^2+15^2$,然后向回算:$500=(1^2+1^2)(5^2+15^2)=10^2+20^2,1000=(1^2+1^2)\cdot500=(1^2+1^2)(10^2+20^2)=10^2+30^2,2000=(1^2+1^2)(10^2+30^2)=20^2+40^2$,这就是其中一组解。

TOP

回复 3# abababa

发网友的解答:
因为$2000=2^4\cdot5^3$,所以整数解的数量是$4\prod_{5}(3+1)=16$,这其中含有负数解,在忽略负数的情况,解的数量是$\frac{16}{4}=4$。
这个得到结果要简单得多,但我没看懂。

TOP

第一个只需遍历1到$\lceil\sqrt{1000}\rceil=32$即可。
第二个问题,$x$遍历1到$\lceil\sqrt{2000/3}\rceil=26$,相应地,$y$ 遍历$\lceil\sqrt{2000-x^2}\rceil$即可。

TOP

回复 5# Infinity
你们在讨论这道题是吧?
http://kuing.orzweb.net/viewthre ... &extra=page%3D1
有没有不用枚举做的?
当然“轻度”枚举还是可以的

TOP

本帖最后由 abababa 于 2018-3-24 18:24 编辑

回复 4# abababa

请网友又帮忙编了一个程序:
  1. n = 9988776543210
  2. while n % 2 == 0:
  3.         n /= 2
  4. betas = {}; d = 3
  5. while n > 1:
  6.         while n % d == 0:
  7.                 if d not in betas:
  8.                         betas[d] = 1
  9.                 else:
  10.                         betas[d] += 1
  11.                 n /= d
  12.         d += 1
  13.         if d * d > n:
  14.                 if n > 1:
  15.                         betas[int(n)] = 1
  16.                 break
  17. num = 1
  18. for k, v in betas.items():
  19.         if k % 4 == 3:
  20.                 if v % 2 == 1:
  21.                         num = 0
  22.                         break
  23.         else:
  24.                 num *= v + 1
  25. print('num of solution is:', num)
复制代码

TOP

回复 6# 其妙

这个和楼主的题还不一样,这个要解出所有的解,而楼主的题只要得到解的数量。

TOP

本帖最后由 abababa 于 2018-3-24 22:48 编辑

回复 6# 其妙

发网友的解答:
只算那个2005的。
不妨设$a>=b>=c$,显然$26<=a<=44$
当$a=26$时$b^2+c^2=1329=3^1\cdot443^1$,因为$3\equiv3\pmod{4}$因此无解
当$a=27$时$b^2+c^2=2^2\cdot11^1\cdot29^1$,因为$11\equiv 3 \pmod{4}$因此无解
当$a=28$时$b^2+c^2=3\cdot11\cdot37$同理无解
当$a=29$时$b^2+c^2=2^2\cdot3\cdot97$同理无解
当$a=30$时$b^2+c^2=1105=5\cdot13\cdot17=(1^2+2^2)(10^2+11^2)=(1\cdot11+2\cdot10)^2+(1\cdot10-2\cdot11)^2=31^2+12^2=(2\cdot11+1\cdot10)^2+(2\cdot10-1\cdot11)^2=32^2+9^2=(1^2+4^2)(1^2+8^2)=(1\cdot1-4\cdot8)^2+(1\cdot8+4\cdot1)^2=31^2+12^2=(4\cdot1-1\cdot8)^2+(4\cdot8+1\cdot1)^2=4^2+33^2$
有解数量为$(1+1)(1+1)(1+1)=8$个,去掉序数变化有$4$解,上面已全部解出,没有其它解。此时满足$a>=b>=c$的只有$(a,b,c)=(30,24,23)$
当$a=31$时由上一解知显然$(a,b,c)=(31,30,12)$是解且再无其它解。
当$a=32$时也易知$(a,b,c)=(32,30,9)$是解且再无其它解。
当$a=33$时也易知$(a,b,c)=(33,30,4)$是解且再无其它解。
当$a=34$时$b^2+c^2=3\cdot283$,同理无解。
当$a=35$时$b^2+c^2=2^2\cdot3\cdot5\cdot13$同理无解。
当$a=36$时$b^2+c^2=709^1=22^2+15^2$,有唯一无序正解,即$(a,b,c)=(36,22,15)$
当$a=37$时$b^2+c^2=2^2\cdot3\cdot53$同理无解
当$a=38$时$b^2+c^2=3\cdot11\cdot17$同理无解
当$a=39$时$b^2+c^2=2^2\cdot11^2$,因为$11\equiv 3\pmod{4}$,因此解的数量是$0$
当$a=40$时$b^2+c^2=3^4\cdot5^1=(1^2+2^2)9^2=9^2+18^2$,因为$2 \mid 4$因此有$(1+1)=2$组正解,无序正解只有一组,即$(a,b,c)=(40,18,9)$
当$a=41$时$b^2+c^2=2^2\cdot3^4$,因为$3\equiv 3\pmod{4}$,因此解的数量是$0$
当$a=42$时$b^2+c^2=241$,因为$241 \equiv 1\pmod{4}$因此无序正解只有$1$组,即$(a,b,c)=(42,15,4)$
当$a=43$时$b^2+c^2=2^2\cdot3\cdot13$同理无解
当$a=44$时$b^2+c^2=3\cdot23$同理无解
上面即为全部解。

TOP

回复 9# abababa
,不过恰恰不定方程$a^2+b^2+c^2=2005$由命题人给出解答了,反而不定方程$a^2+b^2+c^2=2018$还没人给出非软件的解答(允许轻度枚举)

TOP

返回列表 回复 发帖