等差数列
(NumberTheory/Basic/arithmetic_sequence.py)

• View this file on GitHub
• Last update: 2022-01-21 18:13:45+09:00

概要

等差数列に関する基本的な公式

使い方

Arithmetic.get(a0: int, d: int, i: int) -> int
初項 $a_0$ 公差 $d$ の等差数列について $a_i$ を返す。計算量 $O(1)$

Arithmetic.general_term(i: int, ai: int, j: int, aj: int) -> Tuple[Tuple[int, int], Tuple[int, int]]
$a_i$ と $a_j$ を与えたときの、等差数列の初項 $a_0$ 公差 $d$ を返す。$a_0$ と $d$ はそれぞれ (分母, 分子) を表すタプルで返される。計算量 $O(1)$

Arithmetic.sum(a0: int, d: int, r: int) -> int
初項 $a_0$ 公差 $d$ の等差数列について、$a_0 + a_{1} + \ldots + a_{r-1}$ を返す。計算量 $O(1)$

Arithmetic.range_sum(a0: int, d: int, l: int, r: int) -> int
初項 $a_0$ 公差 $d$ の等差数列について、$a_l + a_{l+1} + \ldots + a_{r-1}$ を返す。計算量 $O(1)$

Verified with

• TestCase/unittest/arithmetic_sequence.unittest.test.py

Code

class Arithmetic:
    @staticmethod
    def get(a0, d, i):
        return i * a0 + d

    @staticmethod
    def general_term(i, ai, j, aj):
        def gcd(a, b):
            while b: a, b = b, a % b
            return a

        assert(i != j)
        if i > j:
            i, j = j, i
        gcd_ = gcd(abs(j * ai - i * aj), j - i)
        rational_a0 = ((j * ai - i * aj) // gcd_, (j - i) // gcd_)
        gcd_ = gcd(abs(aj - ai), j - i)
        rational_d = ((aj - ai) // gcd_, (j - i) // gcd_)
        return rational_a0, rational_d

    @staticmethod
    def sum(a0, d, r):
        return r * a0 + d * (r - 1) * r // 2

    @staticmethod
    def range_sum(a0, d, l, r):
        return Arithmetic.sum(a0, d, r) - Arithmetic.sum(a0, d, l)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page