→ Sfly :you forget the terms -2x0bt+2yoat 10/13 03:50
→ doublewhi :幫樓上補充: 2(a-b)t 要改成↑ 10/13 06:43
推 HiJimmy :嗯嗯 謝謝原PO 10/13 08:31
→ ioxy :唉呀呀寫錯了，t= -(ay0-bx0)/(a^2 + b^2) 才對 10/13 10:14
※ 引述《HiJimmy (嗨 吉米)》之銘言：
: 題目
: ax+by=c
: a,b,c 正整數
: x,y整數
: 如果我想用EXCEL算
: 有一個通用的邏輯嗎?
: 我試著用輾轉相除法
: 還有什麼大衍求一術
: 我試著算算看
: 但是
: 那個解都不是最接近(0,0)
: 要讓他最接近(0,0)有無什麼通解(邏輯)?
: 推 S8972616F :(0,0)與線的最短距離 10/12 16:32
: 對齁 算距離我忘了
假設 (a,b)=1，而且這個二元一次方程式是有整數解的。
先找特解 (x0, y0)，利用直線參數式
假設直線上的動點 P(x0-bt, y0+at)
要找最接近 (0,0)，相當於找 OP 距離平方的最小值。
OP 平方 = (a^2 + b^2)t^2 + 2(a-b)t + (x0^2 + y0^2)
在 t = (a-b)/(a^2 + b^2) 時產生最小值，但是因為要
求整數解，所以選擇 [t] 和 [t]+1 代回 P 點比較距離
長短。
整個過程應該可以寫好公式，這樣只要知道 a,b 和特解
就只需比較兩個值。
這是我的想法，也許有簡單一點的流程，畢竟寫程式有些
時候可以用些暴力法，會更快得到答案。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.254.192.252