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.
InputVớ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.
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).
Mỗi test gồm một dòng chứa số x (1 <= x <= 10^5).
Output
Example:
In ra kết quả mỗi test trên một dòng là giá trị của hàm f(x).
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).
- 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:
...