給定一個自然數N，它代表序列 [1,2...N]。我們必須從滿足給定條件的序列中確定對 (x,y) 的數量。
- 1 <= x <= y <= N
- 第一個 x-1 數字的總和（即 的總和
[1,2,3..x-1]）= 從 x 1 到 y 的數字總和（即 的總和[x 1...y]）
示例：-
如果 N = 3，則只有 1 對 (x=1,y=1) 其中 (x-1 個數字的總和) = 0 = (x 1 到 y 的總和)
任何其他對，如 (1, 2),(1,3) 或 (2,3) 不滿足性質。所以答案是 1，因為只有一對。
另一個例子：-
如果 N=10，對于 (6,8) 對，我們可以看到 x-1 個數字的[1,2,3,4,5]總和，即 = 15 = x 1 到 y 的數字總和，即[7,8]另一個這樣的對將是 (1,1 ）。不存在其他這樣的對，因此在這種情況下，答案將是 2。
我們如何處理和解決此類問題以找到此類序列中的對數？
到目前為止，我能夠推斷出的其他事情：-
| 健康）狀況 | 回答 | 對 |
|---|---|---|
| 如果 1<=N<=7 | 1 | {(1,1)} |
| 如果 8<=N<=48 | 2 | {(1,1),(6,8)} |
| 如果 49<=N<=287 | 3 | {(1,1),(6,8),(35,49)} |
| 如果 288<=N<=1680 | 4 | - |
我試過但無法在這些數字中找到任何模式或任何類似的東西。
此外，1<=N<=10^16
uj5u.com熱心網友回復：
- 編輯 -
由 OEIS 提供（評論中的鏈接）：您可以使用以下公式找到 y 的第 k 個值：( (0.25) * (3.0 2.0*(2**0.5))**k ).floor
這給了我們 O(log k) 中的第 k 個值。前幾個結果：
1
8
49
288
1681
9800
57121
332928
1940449
11309768
65918161
384199200
2239277041
13051463048
76069501249
443365544448
2584123765441
15061377048200
87784138523761
511643454094368
2982076586042447
17380816062160312
101302819786919424
590436102659356160
3441313796169217536
20057446674355949568
116903366249966469120
681362750825442836480
3971273138702690287616
23146276081390697054208
134906383349641499377664
786292024016458181771264
4582845760749107960348672
26710782540478185822224384
155681849482119992477483008
907380314352241764747706368
請注意，連續數字的比率很快接近 5.828427124746。給定 n 值，取 n 以 5.828427124746 為底的對數。答案將是接近此日志的整數。
例如，假設 n = 1,000,000,000。然后 log(n, 5.8284271247461) = 11.8。答案可能是 12，但我們可以檢查鄰居來確定。
11: 65,918,161
12: 384,199,200
13: 2,239,277,041
確認的。
-- 結束編輯 --
這是一些 ruby?? 代碼來執行此操作。想法是有兩個指標并酌情增加 x 或 y 的指標。我正在使用 s(n) 來計算總和，盡管這可以通過保持運行總計而無需乘法來完成。
def s(n)
return n*(n 1)/2
end
def f(n)
count = 0
x = 1
y = 1
while y <= n do
if s(x-1) == s(y) - s(x)
count = 1
puts "(#{x}, #{y})"
end
if s(x-1) <= s(y) - s(x)
x = 1
else
y = 1
end
end
end
以下是前幾對：
(1, 1)
(6, 8)
(35, 49)
(204, 288)
(1189, 1681)
(6930, 9800)
(40391, 57121)
(235416, 332928)
(1372105, 1940449)
(7997214, 11309768)
(46611179, 65918161)
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/441739.html
上一篇：將xy坐標（以像素為單位）轉換為重心坐標(x,y,z)
下一篇：如何使用“%”數學運算式？