owned this note
owned this note
Published
Linked with GitHub
## Ước chung lớn nhất (THTB 2021)
$B! = A! \times (A+1) \times (A+2) \times \dots \times (B-1) \times B$
$\Rightarrow \gcd(A!, B!) = A!$.
## PHANSO
**Nhận xét:** Nếu ta có giá trị của $m+p$, ta sẽ có được các giá trị có thể hợp lệ của $n+q$, **và ngược lại**.
Nếu duyệt từng giá trị của $m+p$, với mỗi giá trị tìm ước, thì ta mất $\mathcal{O}(\sqrt{m+p})$. Bản thân $p < m \le 10^{15}$, tức phải chạy $10^15$ lần $\mathcal{O}(\sqrt{m+p})$, nên điều này bất khả thi.
Tuy nhiên, nếu duyệt từng $n$ rồi tìm các bội của mỗi số $n+q$, ta có thể lập công thức tìm số đầu tiên & số cuối cùng, để đếm số lượng.
- Số đầu tiên chia hết cho $T = n+q$:
- Ta thấy $m + p > m$
- $\Rightarrow \left(\left\lfloor\dfrac{m}{T}\right\rfloor + 1\right) \times T$
- Số lớn nhất chia hết cho $T$:
- Ta thấy $m+p < m + (m-1) = 2m-1$
- $\Rightarrow \left\lfloor\dfrac{2m-1}{T}\right\rfloor \times T$
- $\Rightarrow$ đáp án là $\left\lfloor\dfrac{2m-1}{T}\right\rfloor - \left(\left\lfloor\dfrac{m}{T}\right\rfloor + 1\right) + 1 = \left\lfloor\dfrac{2m-1}{T}\right\rfloor - \left\lfloor\dfrac{m}{T}\right\rfloor$
```
ans = 0
for q = 1 -> n-1:
ans += (2 * m - 1) // (n+q) - m // (n+q)
```
## Tổng các chữ số
**Nhận xét:** Ta tính đáp án của bài này với các số từ:
- (1) từ 1 tới $B$
- (2) từ 1 tới $A-1$
Sau đó lấy (2) - (1) để ra kết quả.
Bây giờ, chúng ta sẽ xem cách làm tổng quát để tính tổng các chữ số trong các số từ $1$ tới $N$.
**Riêng trong bài này**, để tiện xử lý, ta có thể coi như số được phép có chữ số $0$ ở đầu.
### Cách giải
Đầu tiên, ta cần xem thử, tổng các chữ số của các số có $x$ chữ số là bao nhiêu? (Tính cả các số có chữ số 0 ở đầu)
Gọi kết quả đó là $f(x)$.
- $f(1) = 45$
- $f(2) = 2 \times 10 \times 45$
- $f(x) = x \times 10^{x-1} \times 45$
Gọi hàng đơn vị là hàng ở cột thứ $0$, hàng chục ở cột $1$, các hàng lớn hơn lần lượt cộng cho $1$
Ta sẽ thử tính:
$N = 2305$, số có $k=4$ chữ số.
- $\overline{0xxx}$: $f(3) + 0 \times 10^3$
- $\overline{1xxx}$: $f(3) + 1 \times 10^3$
- $\overline{2xxx}$:
- $\overline{20xx}$: $f(2) + (2+0) \times 10^2$
- $\overline{21xx}$: $f(2) + (2+1) \times 10^2$
- $\overline{22xx}$: $f(2) + (2+2) \times 10^2$
- $\overline{23xx}$:
- $\overline{230x}$
- $\overline{2300}$: $f(0) + (2+3+0+0) \times 10^0$
- $\overline{2301}$: $f(0) + (2+3+0+1) \times 10^0$
- $\overline{2302}$: $f(0) + (2+3+0+2) \times 10^0$
- $\overline{2303}$: $f(0) + (2+3+0+3) \times 10^0$
- $\overline{2304}$: $f(0) + (2+3+0+4) \times 10^0$
- $\overline{2305}$: $f(0) + (2+3+0+5) \times 10^0$
Nhìn chung các bước là:
- Lần lượt duyệt các hàng $i$ từ $k-1$ về $0$.
- Với mỗi hàng $i$, ta lần lượt điền các chữ số $d$ từ $0$ tới $9$.
- Nếu $d < N_i$, ta tính công thức tổng quát cho các số có dạng (được điền vào $k-i$ chữ số đầu tiên, với chữ số hàng $i$ là $d$ và các chữ số khác tương tự như $N$). (*)
- Nếu $d = N_i$, ta không thể tính tổng quát được, nên chuyển sang hàng tiếp theo (nhỏ hơn) để tiếp tục chia trường hợp như trên.
(*) ta có thể sử dụng một biến lưu tổng các chữ số trước hàng $i$ để dễ tính việc này hơn.
```python=
def f(x):
return x * (10 ** (x-1)) * 45
def calculate(n):
digits = [];
while n > 0:
digits.append(n % 10);
n //= 10
length = len(digits)
prevSum = 0; ans = 0
for i in range(length - 1, 0 - 1, -1):
begin = 0; end = digits[i] - 1
if i == 0: end += 1 # tính cả 2305
for d in range(begin, end+1):
ans += f(i) + (prevSum + d) * (10 ** i)
prevSum += digits[i]
return ans
a, b = int(input())
print(calculate(b) - calculate(a-1))
```
## Tìm chữ số thứ n
### Tìm $u_i$ của $n$
$n$ nằm trong $u_i$, nếu $||u_1|| + ||u_2|| + \dots + ||u_{i-1}|| < n$, và $||u_1|| + ||u_2|| + \dots + ||u_{i-1}|| + ||u_i|| \geq n$
Ta thấy: $f(i) = ||u_1|| + ||u_2|| + \dots + ||u_{i-1}|| + ||u_i|| = 1 + 2 + \dots + i = \dfrac{i(i+1)}{2}$
$\Rightarrow$ tìm $i$ nhỏ nhất sao cho $\dfrac{i(i+1)}{2} \geq n$, sử dụng tìm kiếm nhị phân.
### Tìm vị trí trong $u_i$ của $n$.
vị trí của $u_i$ trong $n$ là: $j = n - f(i-1)$
việc còn lại là xem thử vị trí $j$ này là số nào trong các số từ $1$ tới $9$.
$n = 200$
$u_{20}$ $\Rightarrow$ $j = n-f(19) = 10$
12345678912345678912
```python=
def f(x):
return x * (x+1) // 2
n = int(input())
lo = 1; hi = 10**9; ans = 10**9
while lo <= hi:
mid = (lo + hi) // 2
if f(mid) >= n: # thỏa mãn thì
ans = mid # gán đáp án
hi = mid - 1 # tìm đáp án nhỏ hơn
else: # ngược lại
lo = mid + 1 # tìm số lớn hơn để thỏa mãn
i = ans
j = n - f(i - 1)
j %= 9;
if j == 0: j = 9
print(j)
```