Đây là một bài toán đòi hỏi các bạn phải có sư khéo léo về cách tối ưu thuật toán :)))))
## Hướng đi ban đầu
- Ta chỉ cần thêm chữ số $d$ cho đến khi số đó chia hết cho $n$ thì thôi
- Tuy nhiên, nếu biểu diễn bằng cách bình thường thì số sẽ **rất lớn**
- Và khi kiểm tra xem nó có chia hết cho $n$ hay không thì **rất cực**
- Vì thế, thay vì biểu diễn nguyên số, ta chỉ cần ghi nhận **số dư** của nó là xong. Ta gọi nó là $x$
- Số đó sẽ chia hết cho $n$ khi `x == 0`
## Cách giải quyết trường hợp không có số nào thoả mãn và tối ưu thêm
- Giả sử nghiệm của bài toán là số $\underbrace{\overline{ddd \ldots ddd}}_{\text{m chữ số}}$
- Thì lúc này: $d\times \underbrace{111 \ldots 111}_{\text{m chữ số}} \equiv 0 \pmod n$
- Gọi $g = \gcd(n, d) \Rightarrow \frac{d}{g} \times \underbrace{111 \ldots 111}_{\text{m chữ số}} \equiv 0 \ (\bmod \frac{n}{g})$
- Mà $\frac{d}{g}$ và $\frac{n}{g}$ là hai số nguyên tố cùng nhau nên $\underbrace{111 \ldots 111}_{\text{m chữ số}} \equiv 0 \ (\bmod \frac{n}{g})$
- Vậy thì lúc này bài toán chuyển thành tìm $m$ nhỏ nhất sao cho $\underbrace{111 \ldots 111}_{\text{m chữ số}} \equiv 0 \ (\bmod \frac{n}{g})$
- Và ta đơn giản chỉ cần thực hiện thuật toán $\frac{n}{g}$ lần là đủ
**Mặc dù cách tối ưu này một số người có thể không đồng ý và đỏi hỏi thuật toán tối ưu hơn.**
**Nhưng sau này, lên cấp 3, bạn phải tối ưu từng chút một thế này mới AC được một số bài toán**
**Có bài $n \le 10^5$ độ phức tạp $O(n \log n)$ thì TLE, có bài $n \le 10^3$, độ phức tạp $O(n^3)$ vẫn AC như thường**
```cpp
#include <bits/stdc++.h>
#define int long long
#define taskname "main"
using namespace std;
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(taskname".inp","r",stdin);
freopen(taskname".out","w",stdout);
#endif
int n, d; cin>>n>>d;
if (d == 0)
{
cout<<1;
return 0;
}
int lim = n / __gcd(n, d);
int r = 0;
for (int i = 1; i <= lim; i++)
{
r = (r * 10 + 1) % lim;
if (r == 0)
{
cout<<i;
return 0;
}
}
cout<<0;
}
```
minhpnk2
Created at
1 likes