Original

Тор бус олон өнцөгт доторх торон цэгүүд

Торон олон өнцөгтийн хувьд олон өнцөгт доторх торон цэгүүдийг тоолох Пикийн томьёо байдаг. Дурын оройтой олон өнцөгтийн хувьд яах вэ?

Олон өнцөгтийн ирмэг бүрийг тусад нь боловсруулъя, дараа нь бид ирмэг бүрийн доорх торон цэгүүдийн тоог тэмдэг сонгохын тулд түүний чиглэлийг харгалзан нэмж болно (трапец ашиглан олон өнцөгтийн талбайг тооцоолохтой адил).

Юуны өмнө хэрэв одоогийн ирмэг $A=(x_1;y_1)$ ба $B=(x_2;y_2)$-д үзүүрийн цэгтэй бол түүнийг шугаман функц хэлбэрээр илэрхийлж болохыг тэмдэглэх хэрэгтэй:

$$y=y_1+(y_2-y_1) \cdot \dfrac{x-x_1}{x_2-x_1}=\left(\dfrac{y_2-y_1}{x_2-x_1}\right)\cdot x + \left(\dfrac{y_1x_2-x_1y_2}{x_2-x_1}\right)$$

$$y = k \cdot x + b,~k = \dfrac{y_2-y_1}{x_2-x_1},~b = \dfrac{y_1x_2-x_1y_2}{x_2-x_1}$$

Одоо бид $b' = b + k \cdot \lceil x_1 \rceil$ болохоор $x=x'+\lceil x_1 \rceil$ орлуулгыг хийнэ. Энэ нь бидэнд $x_1'=0$ ба $x_2'=x_2 - \lceil x_1 \rceil$-тэй ажиллах боломж олгоно. $n = \lfloor x_2' \rfloor$ гэж тэмдэглэе.

Алгоритмын бүрэн бүтэн байдлын үүднээс бид $x = n$ дээрх ба $y = 0$ дээрх цэгүүдийг нэмэхгүй. Тэдгээрийг дараа нь гараар нэмж болно. Ингэснээр бид $\sum\limits_{x'=0}^{n - 1} \lfloor k' \cdot x' + b'\rfloor$-г нэмэх ёстой. Мөн бид $k' \geq 0$ ба $b'\geq 0$ гэж үзнэ. Эс бөгөөс $x'=-t$ гэж орлуулж, $b'$ дээр $\lceil|b'|\rceil$-г нэмэх хэрэгтэй.

$\sum\limits_{x=0}^{n - 1} \lfloor k \cdot x + b\rfloor$ нийлбэрийг хэрхэн тооцоолохыг хэлэлцье. Бидэнд хоёр тохиолдол байна:

• $k \geq 1$ or $b \geq 1$.

  Тэгвэл бид $y=\lfloor k \rfloor \cdot x + \lfloor b \rfloor$-ээс доош байгаа цэгүүдийг нэмэхээс эхлэх ёстой. Тэдгээрийн тоо дараахтай тэнцүү

  $$ \sum\limits_{x=0}^{n - 1} \lfloor k \rfloor \cdot x + \lfloor b \rfloor=\dfrac{(\lfloor k \rfloor(n-1)+2\lfloor b \rfloor) n}{2}. $$

  Одоо бид зөвхөн $\lfloor k \rfloor \cdot x + \lfloor b \rfloor < y \leq k\cdot x + b$ байх $(x;y)$ цэгүүдийг сонирхож байна. Энэ тоо нь $0 < y \leq (k - \lfloor k \rfloor) \cdot x + (b - \lfloor b \rfloor)$ байх цэгүүдийн тоотой ижил. Ингэснээр бид бодлогоо $k'= k - \lfloor k \rfloor$, $b' = b - \lfloor b \rfloor$ болгон хураасан ба одоо $k'$ ба $b'$ хоёул $1$-ээс бага байна. Энд зураг байна, бид зүгээр л цэнхэр цэгүүдийг нэмж, $k$ ба $b$-ийн хувьд бодлогыг илүү бага утга руу хураахын тулд хараас цэнхэр шугаман функцийг хассан:

  

• $k < 1$ and $b < 1$.

  Хэрэв $\lfloor k \cdot n + b\rfloor$ нь $0$-тэй тэнцүү бол бид аюулгүйгээр $0$ буцааж болно. Хэрэв тийм биш бол $x < 0$ ба $0 < y \leq k \cdot x + b$ байх торон цэг байхгүй гэж хэлж болно. Энэ нь хэрэв бид $O'=(n;\lfloor k\cdot n + b\rfloor)$ байх, $x'$ тэнхлэг доош чиглэсэн, $y'$ тэнхлэг зүүн тийш чиглэсэн шинэ координатын систем авч үзвэл ижил хариулт авна гэсэн үг юм. Энэ координатын системийн хувьд бид дараах олонлог дээрх торон цэгүүдийг сонирхож байна

  $$ \left\{(x;y)~\bigg|~0 \leq x < \lfloor k \cdot n + b\rfloor,~ 0 < y \leq \dfrac{x+(k\cdot n+b)-\lfloor k\cdot n + b \rfloor}{k}\right\} $$

  энэ нь биднийг $k>1$ тохиолдол руу буцаана. Доорх зурган дээр шинэ координатын эх цэг $O'$ ба $X'$, $Y'$ тэнхлэгүүдийг харж болно:

  
  Таны харж байгаагаар шинэ координатын системд шугаман функц $\tfrac 1 k$ коэффициенттэй байх ба түүний тэг нь $\lfloor k\cdot n + b \rfloor-(k\cdot n+b)$ цэгт байх бөгөөд энэ нь дээрх томьёог зөв болгоно.

Complexity-ийн шинжилгээ

Бид хамгийн ихдээ $\dfrac{(k(n-1)+2b)n}{2}$ цэг тоолох ёстой. Тэдгээрийн дундаас бид хамгийн эхний алхамд $\dfrac{\lfloor k \rfloor (n-1)+2\lfloor b \rfloor}{2}$-г тоолно. Бид $b$-г эхлээд $1$-ээс бага болгож болох тул түүнийг үл ялиг бага гэж үзэж болно. Тэр тохиолдолд бид бүх цэгийн ойролцоогоор $\dfrac{\lfloor k \rfloor}{k} \geq \dfrac 1 2$-г тоолж байна гэж хэлж болно. Ингэснээр бид $O(\log n)$ алхамд дуусна.

Implementation

Here is simple function which calculates number of integer points $(x;y)$ such for $0 \leq x < n$ and $0 < y \leq \lfloor k x+b\rfloor$:

int count_lattices(Fraction k, Fraction b, long long n) {
    auto fk = k.floor();
    auto fb = b.floor();
    auto cnt = 0LL;
    if (k >= 1 || b >= 1) {
        cnt += (fk * (n - 1) + 2 * fb) * n / 2;
        k -= fk;
        b -= fb;
    }
    auto t = k * n + b;
    auto ft = t.floor();
    if (ft >= 1) {
        cnt += count_lattices(1 / k, (t - t.floor()) / k, t.floor());
    }
    return cnt;
}

Here Fraction is some class handling rational numbers. On practice it seems that if all denominators and numerators are at most $C$ by absolute value then in the recursive calls they will be at most $C^2$ if you keep dividing numerators and denominators by their greatest common divisor. Given this assumption we can say that one may use doubles and require accuracy of $\varepsilon^2$ where $\varepsilon$ is accuracy with which $k$ and $b$ are given. That means that in floor one should consider numbers as integer if they differs at most by $\varepsilon^2$ from an integer.