P152PROA PTIT SPOJ – ROUND 2A – Nguyên tố cùng nhau
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROA/ 1. Đề bài P152PROA SPOJ 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ố ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROA/
1. Đề bài P152PROA SPOJ
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
2. Giải thích khái niệm P152PROA SPOJ
– Nguyên tố cùng nhau của 2 số a và b là UCLN của a và b bằng 1
Hướng dẫn:
– Xây dựng hàm UCLN, Kiểm tra số nguyên tố rồi thực hiện duyệt bình thường.
ĐPT: O(n*T)
3. code tham khảo P152PROA SPOJ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | const fi='; type data=longint; var T,N,i,j,dem,k:data; snt:boolean; f:text; function ktsnt(x:data):data; var i:data; begin if x=1 then exit(0); for i:=2 to trunc(sqrt(x)) do if x mod i=0 then exit(0); exit(1); end; function UCLN(a,b:data):data; var r:data; begin while a mod b<>0 do begin r:=a mod b; a:=b; b:=r; end; exit(b); end; begin assign(f,fi); reset(f); readln(f,T); for i:=1 to T do begin readln(f,k); dem:=0; for j:=1 to k do if ucln(k,j)=1 then inc(dem); writeln(ktsnt(dem)); end; close(f); end. |
