Bình luận

• 
  

  0

  

  willingtodo  đã bình luận lúc 11, Tháng 4, 2025, 13:59

  void sieve(int n) {
      for (int i = 0; i <= n; i++) phi[i] = i;
      for (int i = 2; i <= n; i++) {
          if (phi[i] == i) {
              for (int j = i; j <= n; j += i) {
                  phi[j] -= phi[j] / i;
              }
          }
      }
  }
  
  sieve(n);
      for (int i = 1; i <= n; i++) {
          if (phi[i] == i - 1) cout << i << " "; 
          else cout << phi[i] << " ";
      }
  

• 
  

  -1

  

  bengokyeuanh99  đã bình luận lúc 11, Tháng 4, 2025, 11:47

  Đề nói một đằng, ví dụ làm một nẻo làm ngồi check lú lun

  Đề nói: "Tính phi hàm Euler từ 1 đến N" tức là phải in ra phi(1), phi(2), ..., phi(N) theo định nghĩa chuẩn của toán học.

  Nhưng ví dụ lại in:

  phi(5) in ra 5, trong khi kết quả đúng là 4 (vì {1,2,3,4} là 4 số nguyên tố cùng nhau với 5).

  phi(11) in ra 11, trong khi kết quả đúng là 10.

  Bài này bịp ngầm

  Đề yêu cầu 1 đằng, nhưng ví dụ kiểm tra lại là 1 nẻo.

  Nếu code theo đúng định nghĩa phi hàm Euler thì sẽ bị sai test.

  Muốn đúng test thì phải “chơi trò giả ngu”:

  Nếu phi(x) == x - 1 (tức x là số nguyên tố) thì in x luôn,

  Còn lại thì in phi(x) như bình thường

• 
  

  0

  

  bengokyeuanh99  đã bình luận lúc 11, Tháng 4, 2025, 9:25 ← sửa 4 →

  Ùi dời ơi tốn nữa buổi giải bài này Công nhận khoai ác ra Giải bằng py thì bị quá thời gian miết

  Code cho ae tham khảo và cmt trên có giải thích đấy

  include <iostream>

  include <vector>

  using namespace std;

  // Sàng Euler tính mảng phi[] cho 1 đến n // (phi[x] = số lượng số nguyên ≤ x nguyên tố cùng nhau với x) inline vector<int> computeTotients(int n) { vector<int> phi(n + 1); for (int i = 0; i <= n; ++i) { phi[i] = i; } for (int i = 2; i <= n; ++i) { if (phi[i] == i) { // i là số nguyên tố for (int j = i; j <= n; j += i) { phi[j] -= phi[j] / i; } } } return phi; }

  int main() { ios::syncwithstdio(false); cin.tie(nullptr);

  int n;
  cin >> n;
  
  const auto phi = computeTotients(n);
  
  // In kết quả: nếu số nguyên x là số nguyên tố (phi[x] == x - 1)
  // theo đề bài yêu cầu in ra x thay vì phi(x)
  for (int x = 1; x <= n; ++x) {
      if (x > 1) cout.put(' ');
      cout << (phi[x] == x - 1 ? x : phi[x]);
  }
  
  cout.put('\n');
  return 0;
  

  }