Bình luận

• 
  

  9

  jumptozero    8:45 a.m. 19 Tháng 7, 2020 ← chỉnh sửa 3 →

  • Thấy nhiều bạn thảo luận sôi nổi bên nhóm chat về bài này, mình xin chia sẻ lời giải bài này như sau:

  • Gọi \(\tau(d)\) là số ước của \(d\) với \(d\) là số nguyên dương. Ví dụ \(\tau(5)=2\) (Vì \(5\) có \(2\) ước là \(1\) và \(5\)).

  • Khi đó theo đề ta có: \(F(n)=\sum\limits_{d|n}\tau(d)\).

  • Ta có những tính chất quan trọng sau: Nếu \(f\) là \(1\) hàm nhân tính thì hàm xác định bởi công thức \(F(n)=\sum\limits_{d|n}f(d)\) cũng là hàm nhân tính. (Các bạn có thể tham khảo tại \(\href{https://vnoi.info/wiki/algo/math/multiplicative-function}{VNOI}\))

  • Áp dụng tính chất quan trọng này vào bài toán, ta có: Vì \(\tau(d)\) là hàm nhân tính, nên từ đây ta suy ra được \(F(n)\) cũng là hàm nhân tính.

  • Khi đó \(F(n)=F(p_1^{\alpha_1})F(p_2^{\alpha_{2}})...F(p_k^{\alpha_{k}})\) (với \(n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},p_i\in \mathbb{P}\forall i=\overline{1,k}\), trong đó \(\mathbb{P}\) là tập hợp các số nguyên tố)

  • Việc còn lại vô cùng đơn giản đó là ta chỉ tính \(F(p_i^{\alpha_i})\forall i=\overline{1,k}\).

  • Để tính được \(F(p_i^{\alpha_i})\), ta cần chú ý một tính chất quan trọng của hàm \(\tau(d)\) đó là : Nếu \(d=p^{\alpha}(p\in \mathbb{P})\) thì \(\tau(p^{\alpha})=\alpha+1\)

  • Khi đó ta có: \(F(p_i^{\alpha_i})=\sum\limits_{d|p_i^{\alpha_i}}\tau(d)=\tau(1)+\tau(p_i^{1})+...+\tau(p_i^{\alpha_i})=1+2+...+(\alpha_i+1)=\frac{(\alpha_i+1)(\alpha_i+2)}{2}\)

  • Từ đây ta suy ra được: \(F(n)=\prod\limits_{i=1}^{k}\frac{(\alpha_i+1)(\alpha_i+2)}{2}\) với \(n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},p_i\in \mathbb{P}\forall i=\overline{1,k}\)

  • Đến đây công việc còn lại đơn giản đó là phân tích \(n\) thành nhân tử và tính biểu thức trên.

  • Tiếp theo là đến phần code !

  • Ở đây đề bài lại bắt chúng ta tính \(F(n)\) với \(n=N\text{!}\), nên ở đây sẽ có đôi chút kĩ thuật, các bạn đón xem tiếp nhé!

  • Đầu tiên ta có một tính chất khá hay như sau: Nếu \(p\) là số nguyên tố, thì số mũ của \(p\) trong \(N\text{!}\) đó là: \([\frac{N}{p}]+[\frac{N}{p^{2}}]+...+[\frac{N}{p^{k}}]\) với \(N < p^{k+1}\) (Công thức Lagrange)

  • Tiếp theo chúng ta cần tạo trước mảng chứa các số nguyên tố nhỏ hơn \(10^6\), làm tiền đề để tính các \(\alpha_i\), các bạn có thể tham khảo code tại đây !

  const ll  N = 1000000;
  ll  lp[N+1];
  vector<ll > pr;
  void solve(){
  for (ll  i=2; i<=N; ++i) {
      if (lp[i] == 0) {
          lp[i] = i;
          pr.push_back (i);
      }
      for (ll  j=0; j<(ll )pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
          lp[i * pr[j]] = pr[j];
  }
  }
  

  Và công việc còn lại chỉ là đi tính từng \(\alpha_i\), cái này xin dành cho bạn đọc (Cũng đơn giản thôi !)

  • Và cuối cùng là đi tính \(F(n)\text{ % } mod\) là xong. Như vậy là bài toán đã được giải quyết

  • Dưới đây là code của mình, các bạn có thể tham khảo tại \(\href{https://ideone.com/DB015Z}{đây}\)

  • P/s: Nếu có gì sai hoặc khó hiểu hoặc thắc mắc, các bạn cứ comment nhé !

3 bình luận nữa