ĐỒ ÁN MÔN HỌC NM CNTT1 - BÀI 1

ĐỒ ÁN MÔN HỌC NM CNTT1

LỚP CỬ NHÂN TÀI NĂNG KHÓA 2012

Giảng viên ra đề:

ThS. Trương Phước Hưng

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⁹

Ví dụ:

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

Bài làm

-         Nhận xét ban đầu:

o   A^A luôn chia hết cho A nên chắc chắn kết quả N ≤ A. Vậy ta có thể lặp tìm N từ 1 đến A, gặp số N nào thoả N^N chia hết A thì ta dừng. Nhưng cách làm này gặp 2 vấn đề: N^N tăng rất nhanh và nếu lặp từ 1 đến 10⁹ thì chương trình sẽ chạy khá chậm.

o   Do chỉ cần xét N^N có chia hết cho A hay không mà không cần quan tâm kết quả này nên ta có thể phân tích N và A ra thừa số nguyên tố để kiểm tra tính chia hết. Như vậy sẽ không lo N^N tràn số. Nhưng chương trình vẫn phải duyệt từ 1 đến A nên vẫn chậm.

-         Đầu tiên, ta sẽ phân tích A và N ra tích các thừa số nguyên tố để dễ xét tính chia hết:

A = p₁^x1 p₂^x2 … p_k^xk

N = q₁^y1 q₂^y2 … q_m^xm

=> N^N = q₁^y1*N q₂^y2*N … q_m^xm*N

o   Trong cách phân tích này, ta thấy rằng mọi thừa số nguyên tố p_i  của A đều phải chứa trong N. Bởi vì nếu không có p_i thì tất cả các số nguyên tố q_j đều không chia hết cho p_i => N^N không chia hết cho A. Vậy nếu đặt r = p₁p₂…p_k, ta có N ≥ r. Ngoài ra, để N^N chia hết cho A thì mọi số mũ của p_i trong N^N phải lớn hơn hoặc bằng số mũ của p_i trong A. (*)  

-         Vậy N sẽ có dạng: r*t = p₁p₂… p_k* t.
o   Trong trường hợp r ≥ x_i ∀i thì ta chỉ cần đặt N = r thì khi đó N^N = p₁^rp₂^r… p_k^r => mọi số mũ của p_i trong N^N đều lớn hơn hoặc bằng số mũ của p_i trong A => N^N chia hết cho A theo (*).

o   Trong trường hợp ngược lại (tức ∃i : r < x_i), kết quả sẽ là N=r*t với t>1. Lúc này, ta sẽ phải xét t trong khoảng [2,max(x_i)] (chỉ xét đến max(x_i) là vì khi t=max(x_i) thì z_i*t ≥ x_i ∀i => N^N đã chia hết cho A, vậy không cần tìm t lớn hơn max(x_i) nữa). Khi đó, với mỗi ước p_i của A, ta xét số mũ của p_i trong N^N = p₁ ^r*tp₂^r*t… p_k^r*t t^r*t  có lớn hơn số mũ của p_i trong A không. Nếu mọi số mũ p_i trong N^N đều lớn hơn hoặc bằng số mũ của p_i trong A thì N^N sẽ chia hết cho A (theo (*)) => N=r*t chính là giá trị nhỏ nhất để N^N chia hết cho A.

Mã nguồn

#include <iostream>
#include <cmath>
using namespace std;

int demMu(int& iSo, int iUoc)
{
 int iDem = 0;
 while (iSo % iUoc == 0)
 {
  iSo /= iUoc;
  iDem++;
 }
 return iDem;
}

void main()
{
 int iA, iMaxMu = 1, iR = 1;
 cout << "Nhap gia tri cua A: ";
 cin >> iA;
 double dCanA = sqrt(iA * 1.0);
 int iABanDau = iA;

 for (int i = 2; i <= dCanA; i++)
  if (iA % i == 0)
  {
   int iMu = demMu(iA, i); 
   iR *= i;
   if (iMu > iMaxMu)
    iMaxMu = iMu;
  }

 if (iA > 1)
  iR *= iA;

 if (iMaxMu > iR)
  for (int k = 2; k <= iMaxMu; k++)
  {
   bool bEnd = true;
   iA = iABanDau;
   for (int i = 2; i <= dCanA; i++)
    if (iA % i == 0)
    {
     int iC = iR * k;
     int iMuA = demMu(iA, i);
     int iMuC = demMu(iC, i); 

     if (iMuC * iR * k < iMuA)
      bEnd = false;
    }
   if (bEnd) 
   {
    iR *= k;
    break;
   }
  }

 cout << "N nho nhat thoa N^N chia het cho A la: ";
 cout << iR << endl;
}