Bình luận

• 
  

  25

  SPyofgame    11:02 p.m. 10 Tháng 6, 2020 ← chỉnh sửa 3 →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Chia dần các ước nguyên tố của \(n\) đồng thời tăng biến đếm

  Đưa các ước nguyên tố \(p\) và số lần bị chia vào một mảng
  Xuất các số nguyên tố theo tần số

  ---

  Hint 2

  • Khi \((p\ |\ n)\) thì \(p * \frac{n}{p} = n\)

  \(\Leftrightarrow p\) là ước của \(n\) thì \(\frac{n}{p}\) cũng là ước của \(n\)

  Ta có thể chạy tới \(\sqrt{n}\) để đếm số ước

  • Thay vì thử từng số nguyên tố, ta có thể từng số \(i\) tăng dần từ 2 và kiểm tra tính chia hết

  Nếu \(n\) không chia hết \(i\) thì bỏ qua (vì nó không phải ước nguyên tố)

  Ngược lại ta sẽ thêm số nguyên tố \(i\) vào mảng và chia \(n\) dần đồng thời tăng số lần chia

  ---

  Hint 3

  • Có \(n = p_1 ^ {f_1} \times p_2 ^ {f_2} \times ... \times p_k ^ {f_k}\) với \(f_i \in N\)

  Thì \(d = p_1 ^ {f''_1} \times p_2 ^ {f''_2} \times ... \times p_k ^ {f''_k}\) là ước của \(n\) \(\forall f''_i ≤ f_i\) và \(f''_i \in N\)

  Mỗi ước nguyên tố \(pi\) có \(f''_i\) cách chọn

  Nên số cách chọn phần tử \(d\) là \((f''_1 + 1) \times (f''_2 + 1) \times ... \times (f''k + 1)\)

  Vậy khi phân tích số nguyên tố từ \(n\) ta dễ dàng tìm số ước trong \(O(log (log n))\)

  • Nhận xét rằng nếu với mọi số nguyên \(2 ≤ x ≤ √n\) không phải là ước của \(n\) thì \(n\) là số nguyên tố

  Chạy tới √n hoặc tới khi \(n = 1\) để phân tích thừa số nguyên tố

  Nếu sau đó \(n > 1\) thì \(n\) là số nguyên tố

  Reference AC code | \(O(\sqrt n)\) time | \(O(\frac{\log n}{\log(\log n)})\) auxiliary space | Factorization

  C++

  int main()
  {
      //// Input
      int n = readInt();
      int sqrtn = sqrt(n);
  
      pair<int, int> divs; /// Divisors vector<p, f> = <prime divisor, frequency>
  
      /// p = 2 case
      if (n % 2 == 0)
      {
          divs.push_back(make_pair(2, 0)); /// Add new prime p = (2)
          do divs.back().se++, n /= 2; while (n % 2 == 0);
      }
  
      /// prime > 2 is odd, we dont have to care about even numbers
      for (int i = 3; i <= sqrtn; i += 2)
      {
          if (n % i != 0) continue;
          divs.push_back(make_pair(i, 0)); /// Add new prime p = (i)
          do divs.back().se++, n /= i; while (n % i == 0);
          if (n == 1) break; /// we can divide more
      }
  
      /// n is prime
      if (n > 1) divs.push_back(make_pair(n, 1));
  
      /// Output
      int p = divs.size();
      int count = 1;
      for (int i = 0; i + 1 < p; ++i)
      {
          count *= (divs[i].second + 1);
          while (divs[i].second-->0) cout << divs[i].first << '*';
      }
      count *= (divs.back().second + 1);
      while (divs.back().second-->1) cout << divs.back().first << '*';
      cout << divs.back().first << endl;
  
      cout << count; /// Number of divisors
      return 0;
  }
  

• 
  

  0

  Quan2212    8:19 p.m. 6 Tháng 10, 2021

  cho hỏi là trong python thì làm sao để xuất dấu nhân cùng với số thế

• 
  

  0

  minhtrietn    3:39 p.m. 30 Tháng 7, 2022

  vd:
  a=1
  b=2
  print(a,'*',b)

  OUTPUT:

  1*2

• 
  

  -1

  tkLeHoangLong    10:42 p.m. 4 Tháng 6, 2023

  sai nha bạn nếu dấu phẩy thì
  OUTPUT :
  1 * 2
  nên cho tiện thì xài: print(str(a)+'*'+str(b))
6 bình luận nữa