[NTUCoder] UOCLE – Ước lẻ

Đề bài: http://laptrinh.ntu.edu.vn/Problem/Details/3267

 Lời giải:
+ Đầu tiên ta chứng minh: Số tự nhiên N có số ước là lẻ <=> N là số chính phương.
Thực vậy, phân tích N thành thừa số nguyên tố: N = p1^a1 * p2^a2 … * pm^am, như vậy số ước của N = (a1 + 1) * (a2 + 1) * .. * (am + 1). Muốn tích này lẻ thì mỗi thừa số (ai + 1) phải lẻ => ai chẳn => N có thể được viết dưới dạng N = [p1^(a1/2) * .. * pm^(am/2)] ^ 2 => N chính phương
+ Vậy Số số có ước lẻ nhỏ hơn bằng N = Số số chính phương nhỏ hơn bằng N = sqrt(N) (Các số chính phương này có được bằng cách bình phương các số từ 1..sqrt(N))

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s