Bình luận

• 
  

  -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ở.

6 bình luận nữa