Cặp số nguyên tố cùng nhau (bài 1 - đề thi chuyên tin Thái Nguyên năm 2025)
Xem dạng PDFHai số nguyên tố cùng nhau là hai số có ước chung lớn nhất bằng 1.
Yêu cầu: Cho số nguyên dương n. Tìm số lượng các số nguyên dương x nhỏ hơn n thoả mãn: x và n là hai số nguyên tố cùng nhau.
Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím) số nguyên dương n (2 ≤ n ≤ 2 x 10^6)
Kết quả: Một số nguyên duy nhất là số lượng các số nguyên dương x, nhỏ hơn n và nguyên tổ cùng nhau với n.
Ví dụ:
Input 01:
4
Output 01:
2
Giải thích: n = 4, trong 3 số 1, 2, 3 nhỏ hơn n, có 2 số thoa mãn: x = 1, 3 là các số nguyên tố cùng nhau với n.
Input 02:
15
Output 02:
8
Giải thích: n = 15, trong 14 số 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 nhỏ hơn n, có 8 số thoa mãn: x = 1, 2, 4, 7, 8, 11, 13, 14 là các số nguyên tố cùng nhau với n.
Giới hạn:
• Có 70% số điểm thoả mãn: 2 ≤ n ≤ 2 x 10^3.
• Có 30% số điểm thoả mãn: 2 x 10^3 < n ≤ 2 x 10^6.
Bình luận
include<bits/stdc++.h>
using namespace std; long long n,cnt=0,k,tong=0,u,x,ma=0,q,l,r,t=-1e9,m=1e9; main() { cin>>n; for(int i=1;i<n;i++){ t=i; x=__gcd(n,t); if(x==1){ cnt++; } } cout<<cnt; }
include <bits/stdc++.h>
using namespace std;
int main()
{
}
//thêm dấu # trước include <bits/stdc++.h>