Bài tập 1

Đề bài: Cho số tự nhiên A. Hãy tìm số tự nhiên N nhỏ nhất sao cho N lũy thừa N (nhân N cho chính nó N lần) chia hết cho A. Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị: 1 ≤ A ≤ 109.

Hướng giải quyết:

Theo tài liệu tìm được trên google và tham khảo từ các bạn thì ta có:

Phân tích số a và n ra thừa số nguyên tố với n bắt đầu từ 2.
a=a1^k1 x a2^k2 x…ai^ki với (a1<a2 <…<i)
n=n1^m1 x n2^m2 x…nj^mj với (n1<n2<…<j)

Khi mà có n[t]>=a[t] và i>=j và n*m[t]>k[t] với t không vượt quả i,j thì ta đã tìm được số thỏa mãn yêu cầu của đề bài.

Do không được sử dụng mảng nên trong khi phân tích ta sẽ so sánh nếu số n đó không thỏa, ta sẽ tăng n lên và phân tích a lại từ đầu rồi tiếp tục so sánh. Ta sử dụng thêm các biến tạm để lưu giá trị của a,n trong khi phân tích và so sánh. Ngoài ra sử dụng thêm các biến đếm số mũ.

 

Mã nguồn. <—- Nhấp vào đây để tải mã nguồn.

Các bạn vào comment thảo luận nha 🙂

Advertisements

About notpeo

roamer
This entry was posted in Uncategorized. Bookmark the permalink.

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