Bình luận

• 
  

  0

  

  Huy_inIT  đã bình luận lúc 8, Tháng 6, 2025, 14:49 ← chỉnh sửa →

  Cách mình chứng minh nha, nếu có sai sót về mặt toán học thì xin mng góp ý ạ, mình không rành latex nên viết vậy thôi à, nếu hữu ích thì cho mình xin Upvote nha hẹ hẹ

  • Giả sử ta có điều kiện: $$ (A \times S) \mod K = 0 \quad \Rightarrow \quad A \times S \equiv 0 \pmod{K} $$
  • Gọi $$d = \gcd(A, K)$$
  • Ta có thể phân tích: $$ A = d \cdot a, \quad K = d \cdot k \quad \text{với } \gcd(a, k) = 1 $$ $$ (d \cdot a) \cdot S \equiv 0 \pmod{d \cdot k} \Rightarrow a \cdot S \equiv 0 \pmod{k} $$
  • Vì $\gcd(a, k) = 1$, nên có nghịch đảo module $a^{-1}$, nhân hai vế cho $a^{-1}$ ta có: $$ S \equiv 0 \pmod{k} $$ $$ K = \gcd(A, K) \cdot k \quad \\ \Rightarrow k = \frac{K}{\gcd(A, K)} $$ $$ \Rightarrow S \equiv 0 \pmod{\frac{K}{gcd(A, K)}} $$ $$ K = \gcd(A, K) \cdot k \quad \\ \Rightarrow k = \frac{K}{\gcd(A, K)} $$ Vậy ta cần tìm số nguyên $S$ trong đoạn $L, R$ sao cho $$S \mod \frac{K}{\gcd(A, K)} = 0$$ -> Cho nên số lượng trong đoạn $L, R$ là $$\frac{R}{\frac{K}{\gcd(A, K)}} - \frac{L - 1}{\frac{K}{\gcd(A, K)}}$$
• 
  

  2

  

  wipad0310  đã bình luận lúc 15, Tháng 1, 2024, 15:02 ← chỉnh sửa →

  T_T Sao mình làm mà có 15 test output bị thiếu mất 1 số so với đáp án thế nhỉ ??

• 
  

  60

  

  Gao_Pink  đã bình luận lúc 14, Tháng 11, 2022, 8:51

  * ~Thấy~ ~hay~ ~cho~ ~xin~ ^ ~nha~ ~!!!~ *

  • Dễ thấy : Nếu ~A~%~K~ = ~0~ thì đáp án luôn là từ đoạn ~L~ ~=>~ ~R~

  • Ngược lại ta phải cần tìm ~X~ nhỏ nhất sao cho ~(X*A)~%~K~ = ~0~ .

  • Như vậy số ~S~ cần tìm có dạng ~X*P~ , ta chỉ cần đếm xem có bao nhiêu số ~P~ thỏa mãn ~L~ ~<=~ ~X*P~ ~<=~ ~R~ .

  • Để tìm ~X~ ta chỉ cần dùng ~K/GCD(A,K)~.

• 
  

  29

  

  DyIuWhite  đã bình luận lúc 21, Tháng 10, 2022, 0:31

  bài này dùng công thức sao vẫn sai nhỉ ??

• 
  

  -2

  

  hh123123  đã bình luận lúc 21, Tháng 10, 2022, 8:31

  Vì công thức không đúng đó mà