Bình luận

• 
  

  -5

  tk22dangminhduc    9:43 p.m. 11 Tháng 7, 2023

  một phiên bản dễ hơn của "FACTOR"...mãi vẫn chưa AC được bài đấy:")

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

• 
  

  2

  hieuhfgr    10:41 a.m. 3 Tháng 5, 2023

  mình nghĩ bài này testcases đang yếu '-'

• 
  

  -2

  tienduyyl    5:14 p.m. 15 Tháng 10, 2021 ← đã chỉnh sửa →

  i

• 
  

  -7

  phambinminh12345    5:44 p.m. 12 Tháng 10, 2021

  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∗np=n
  ⇔p là ước của n thì np cũng là ước của n
  Ta có thể chạy tới 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=pf11×pf22×...×pfkk với fi∈N
  Thì d=pf′′11×pf′′22×...×pf′′kk là ước của n ∀f′′i≤fi và f′′i∈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)×(f′′2+1)×...×(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(logn))
  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(n−−√) time | O(lognlog(logn)) auxiliary space | Factorization
  Copy
  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;
  

  }

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

• 
  

  -6

  phambinminh12345    5:44 p.m. 12 Tháng 10, 2021

  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∗np=n
  ⇔p là ước của n thì np cũng là ước của n
  Ta có thể chạy tới 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=pf11×pf22×...×pfkk với fi∈N
  Thì d=pf′′11×pf′′22×...×pf′′kk là ước của n ∀f′′i≤fi và f′′i∈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)×(f′′2+1)×...×(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(logn))
  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(n−−√) time | O(lognlog(logn)) auxiliary space | Factorization
  Copy
  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;
  

  }

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

• 
  

  -17

  minhtuanitk20    3:53 p.m. 1 Tháng 10, 2021

  bài dễ nhất thế giới

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

  1 phản hồi
• 
  

  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;
  }
  

  1 phản hồi