Đồ án NMCNTT1: 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 (hâ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⁹

Ví dụ:

Số nhập vào là A	Số xuất ra là N
8	4
13	13

Nhận xét: Bài toán đòi hỏi phải tìm số nguyên nhỏ nhất dạng N^N chia hết cho số nguyên A được nhập vào từ bàn phím. Dễ thấy nếu N = A thì hiển nhiên A^A  chia hết cho A vì vậy ta luôn có N ≤ A. Trong trường hợp  A nhỏ bài toán có thể dễ dàn giải quyết bằng cách duyệt từ 0 tới A, tính  N^N và kiểm tra điều kiện chia hết cho A.
Nhưng vấn đề của bài toán này là khi N lớn (xấp xỉ 1 tỉ) thì N^N Có giá trị rất lớn mà không có một kiểu dữ liệu căn bản nào có thể chứa được. Vì vậy ở đây ta sẽ đi tìm một giải pháp khác mà không phải tính toán số cực lớn N^N
 Dễ thấy A luôn có thể phân tích thành tích lũy thừa các số nguyên tố   A = p₁^x1 p₂^x2 … p_k^xk  Do đó điều kiện cần để N^N chia hết cho A là N chia hết cho tích T =p₁p₂ … p_k (Ta có thể chứng minh điều này đễ dàn bằng phản chứng). Ta đăt N = T * i  (i ≤ N)  Khi đó N^N = (T*i)^T*i  = T^T*i * i^T*i  (với T = P₁P₂....P_k)
Ta tìm điều kiện đủ để NN chia hết cho A:
    Gọi Xmax = MAX{x1, x2.....xn} khi đó nếu N= T*i ≥ Xmax lúc đó  T^T*i sẽ chia hết cho A vì vậy N^N chia hết cho A. Vì T, Xmax luôn là hằng số với mỗi giá trị nhập vào của A ta sẽ có i ≥ Xmax \ T bài toán trở thành tìm giá trị nhỏ nhất của i thỏa mãn i ≥ Xmax \ T.
Qua các bước phân tích ở trên, bài toán sẽ được giải thông qua các bước sau:

1. Phân tích A ra tích lũy thừa nguyên tố dạng A = p₁^x1 p₂^x2 … p_k^xk  Tính T = p1p2...pn và Xmax = Max{x1,x2, ...xn}
2. Tìm giá trị nhỏ nhất thỏa mãn i ≥ Xmax \ T
3. Xuất ra kết quả N = T * i

Sau đây là code bài toán

  
#include <iostream>
#include <conio.h>
using namespace std;

int PhanTichNguyenTo( int soNhap, int& Xmax);
bool isPrime(int num);
void NhapXuat();

void main()
{
 
 NhapXuat();
}

void NhapXuat()
{
 int Xmax = 0;
 int A ;
 int i;
 while((cout << endl<< "Nhap so A = ")&&cin >> A)
 {
  int temp = PhanTichNguyenTo(A,Xmax);
     i = ceil(Xmax/(float)temp);
     cout  << "So N nho nhat thoa man dieu kien tren la " << temp * i;
 }
}
/*Ham tra ve tich cac uoc nguyen to cua so nhap 
va so mu lon nhat cua tich nguyen to*/
int PhanTichNguyenTo( int soNhap, int& Xmax)
{
 int T=1;
 int maxExp = 0;

 if(isPrime(soNhap))
 {
  maxExp =1;
  T= soNhap;
 }
 else
  for(int i = 2; i <= sqrt(soNhap); i++)
  {
   int j = 0;
     if(isPrime(i) && (soNhap % i ==0))
     {
      T *= i;
      int temp = soNhap;
      int exp =0;
      while(temp % i ==0)
      {
       temp = temp / i;
       exp++;
      }
   
      if(maxExp < exp)  maxExp = exp;
     }
  }
 
 Xmax = maxExp;
 return T;
}


 bool isPrime(int num)
  {
  bool result = true;
  if(num == 0|| num == 1)
    result = false;
  else
  {
    num = abs(num);

    for(int i = 2; i <= sqrt(num); i++)
    if(num % i == 0)
   result = false;
  }

  return result;
 }