P152PROA - ROUND 2A - Nguyên Tố Cùng Nhau - E16CN PTIT

Trang chủ » Nguyên Tố Cùng Nhau C++ » P152PROA - ROUND 2A - Nguyên Tố Cùng Nhau - E16CN PTIT

Có thể bạn quan tâm

E16CN PTIT

Menu
  • Tin Tức
  • Series
    • Data Structures And Alogrithms
  • Lập Trình
    • Unity
    • Web
    • Android
    • iOS
  • CMCN 4.0
    • AI
    • IoT
    • Big Data
  • Game
  • Tiếng Anh
    • TOEIC
    • IELTS
    • TOEFL
  • Tài Liệu
E16CN PTIT C++ Luyện Tập PTIT SPOJ Toán P152PROA - ROUND 2A - Nguyên tố cùng nhau P152PROA - ROUND 2A - Nguyên tố cùng nhau Thứ Sáu, tháng 9 14, 2018 C++ Luyện Tập PTIT SPOJ Toán
Link Sub: https://www.spoj.com/PTIT/problems/P152PROA/ Người Gửi: Dương Lee

  • Problem:

Juggernaut được cô giáo Disruptor dạy toán, cô giáo định nghĩa một hàm f(x) như sau: Với t là số lượng các số tự nhiên k (1 <= k <= x) thỏa mãn nguyên tố cùng nhau với x, nếu t là nguyên tố thì f(x) = 1, ngược lại f(x) = 0. Disruptor cho Juggernaut một số nguyên dương x, yêu cầu anh cho biết giá trị của hàm f(x), nếu trả lời sai thì Jug sẽ bị cô trả về nhà, Jug không muốn về nhà, các bạn hãy giúp Jug giải bài toán này. Input Dòng đầu tiên chứa số bộ test T (T <= 10). Mỗi test gồm một dòng chứa số x (1 <= x <= 10^5). Output In ra kết quả mỗi test trên một dòng là giá trị của hàm f(x). Example: Input 2 2 3 Output: 0 1

  • Solution:

- Không biết có cách làm toán cao cấp gì không nhưng mình làm theo đề bài với độ phức tạp O(NlogN) vẫn ok. - Tìm số nguyên tố cùng nhau (là hai số có ước chung lớn nhất = 1) bằng phương pháp Euclid. - Sau khi đếm số nguyên tố cùng nhau rồi thì ta tiến hành kiểm tra số nguyên tố và đưa ra kết quả f(x).

  • Code:

C++:

https://ideone.com/n70HhO
#include <iostream> #include <math.h> using namespace std; int ucln(int a, int b) { while (b!=0) { int x = a%b; a = b; b = x; } return a; } int snt(int x) { if (x<2) return 0; for (int i=2; i<=sqrt(x); i++) if (x%i==0) return 0; return 1; } int main() { int T; cin>>T; while(T--) { int x; cin>>x; int d = 0; for (int i=1; i<=x; i++) { if (ucln(i, x)==1) d++; } if (snt(d)==1) cout<<"1"<<endl; else cout<<"0"<<endl; } return 0; }

JAVA:

...

Python:

... DL

Author : DL

Share this

Related Posts

Next « Prev Post Previous Next Post » Đăng ký: Đăng Nhận xét (Atom)

Status

- Để đảm bảo tốc độ load trang: Web sẽ dùng "text" thay vì sử dụng "embed" cho việc hiển thị code. Điều này dẫn đến việc "có thể cósai sót" trong việc hiển thị code. Vậy nên nếu có lỗi bạn có thể sử dụng "link view" đã đính kèm sẵn và báo lỗi ngay comment.
- Loading... Up/350+ Done/700+ SPOJ PTIT

Tiện Ích

  • Yêu Cầu Giải Đáp
  • Thắc Mắc, Góp Ý, Báo Lỗi

Giải thuật và Cấu trúc dữ liệu

Toán 84 Xâu 37 Mảng Đánh Dấu 23 Quy Hoạch Động 16 Sắp Xếp 15 Sinh 13 Tham Lam 8 BFS 7 Stack 7 Tìm Kiếm Nhị Phân 6 Đệ Quy 6 Đồ Thị 6 DFS 5 Quay Lui 4 Quy Luật 4 Sàng nguyên tố Eratosthenes 3 Sắp Xếp Nổi Bọt 3 Queue 2 Danh Sách Liên Kết Kép 1 Kruskal 1 Map 1 Nhánh Cận 1 Phân Tập 1

Ngôn ngữ

C++ (190) C (23) Python (2) Java (1)

Trang luyện tập

  • PTIT SPOJ (205)
  • VN SPOJ (5)

Bài đăng HOT

  • Bảng quy đổi điểm Tiếng Anh và quy định miễn học, miễn thi, chuyển đổi điểm PTIT Bảng quy đổi điểm Tiếng Anh và quy định miễn học, miễn thi, chuyển đổi điểm PTIT
  • PTIT127C - Bố trí phòng họp PTIT127C - Bố trí phòng họp
  • C11PAIRS - Đếm cặp C11PAIRS - Đếm cặp
  • P145PROI - ROUND 5I - Mật khẩu
  • P157PROE - ROUND 7E - Kim cương
  • KPLANK - Bán dừa KPLANK - Bán dừa
  • PTIT125I - Xóa chữ số
  • P155SUMD - ROUND 5D - Chỉ là sắp xếp

Cấp độ

  • Luyện Tập (150)
  • Phát Triển (40)
  • Nhập Môn (20)

Lưu trữ

Lưu trữ tháng 12 2020 (3) tháng 11 2020 (1) tháng 5 2019 (1) tháng 4 2019 (3) tháng 3 2019 (2) tháng 9 2018 (2) tháng 7 2018 (7) tháng 6 2018 (2) tháng 5 2018 (2) tháng 4 2018 (8) tháng 3 2018 (1) tháng 2 2018 (4) tháng 1 2018 (17) tháng 12 2017 (171)

Tổng số lượt xem trang

Từ khóa » Nguyên Tố Cùng Nhau C++