Bài tập Nhập môn CNTT1

Cách giải bài tập Nhập môn CNTT1

Bài 1:

Bài 1:   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 ≤ 10^9

 Ví dụ:

Số nhập vào A		Kết quả
8	4
13	13

Hướng suy nghĩ:         Số N^N chia hết cho A, ta tìm cách phân tích A thành tích các thừa số nguyên tố. Khi đó N^N muốn chia hết cho A thì N phải có đủ hết các số nguyên tố trong cấu thành của A. 
Và khi lấy N^N lên thì mỗi thừa số nguyên tố của N^N đều có mũ lớn hớn mũ của nó trong A.
Ví dụ đơn giản như A được phân tích thành 2^3*3^2.
Thì N phải có dạng 2*3*k
Như vậy thì N^N mới có thể chia hết cho A được. Giả sử ngược lại N không có thừa số 2 hay 3 trong cách phân tích thì khi đem mũ lên cũng sẽ không có thừa số đó trong N^N, do đó chắc chắn không chia hết cho A. Vậy cách làm của ta là lấy mỗi số nguyên tố tạo thành A nhân lại, được số P. Nếu P chưa đủ để P^P chia hết cho A, tức là có một số mũ của phân tích số nguyên tố của A lớn hơn P, ta nhân P cho 2, 3, 4... đến khi nào thỏa thì thôi. Mỗi lần nhân thêm, ta cần chú ý số ta nhân vào góp thêm số mũ cho các thừa số nguyên tố. Chẳng hạn khi ta nhân 4 thì ta không quên là số này có chứa 2 thừa số 2. Do đó ta phải kiểm tra thêm điều này.

Khi nhân theo kiểu này, do ta đã có đủ số nguyên tố, chỉ thiếu số mũ nên kết quả sẽ ra rất nhanh, vì N^N tăng rất nhanh, vì vậy sẽ đảm bảo thời gian chạy.

 Ta có đoạn mã như sau:

1. #include <iostream>

2. #include <cmath>

3. using namespace std;
4.

5. void main()

6. {

7. int a,dem=0,i,p;

8. int max=1;

9. cin >> a;

0. int U[10000],D[10000];

11.p=a;

12.

13.

14. for (i=2;i<=(int)sqrt((float)a);i++)

15. if (p%i==0) {

16. dem++;

17. U[dem]=i;

18. D[dem]=0;

19. while (p%i==0) {

20. D[dem]++;

21. p=p/i;

22. }

23. if (D[dem]>max)

24. max=D[dem];

25. }

26. if (p>1) {

27. dem++;

28. U[dem]=p;

29. D[dem]=1;

30. }

31. p=1;

32. for (i=1;i<=dem;i++)

33. p=p*U[i];

34.//Nhan them va kiem tra lai

35. int phu,j,z,k,kt;

36. for (i=1;;i++) {

37. kt=1;

38. phu=i;

39. for (j=1;j<=dem;j++) {

40. z=0;

41. while (phu%U[j]==0) { 

42. z++;  /*z la so mu cua cua thua so nguyen to j, trong so i 43.  dang duoc nhan them vao */

44. phu=phu/U[j];

45. }

46. if ((z+1)*p*i<D[j]) 

47. kt=0;

48. }

49. if (kt) break;

50. }

51. p=p*i;

52. cout << p << endl;

53.}