Bài tập 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⁹

Ví dụ:

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

 Giải:

Để tìm N nhỏ nhất ta không thể cho N chạy từ 1 đến A, rồi kiểm tra N^N có chia hết cho A không. Nếu A nhỏ thì chỉ không quan tâm nhưng khi A lớn thì giá trị N^N rất lớn có thể xảy ra tràn số.

VD: A =999907 thì N =999907 thì đôi khi thuật toán rất chậm và có thể xảy ra tràn số.Do đó ta phải đi theo con đường khác.

Như đã biết một số nếu là hợp số có thể phân tích thành tích các thừa số là các số nguyên tố. Hiển nhiên bởi số nguyên tố là số chỉ chia hết cho 1 và chính nó.

Từ điều này ta có điều kiện cần để một số chia hết cho A cho trước thì nó phải chia hết hay tích của nó có chứa tất cả thừa số nguyên tố của A.

Xét số aⁿ để chia hết các thừa số nguyên tố của A thì a cũng phải thỏa điều kiện đó.

Có thể hiều là : A =a₁^b1 x a₂^b2 x … x a_n^bn.({a_n} là tập hợp thừa số nguyên tố của  A)

aⁿ mod A = 0 => (aⁿ mod a₁ = 0) /\ (aⁿ mod a₂= 0) /\ …/\ (aⁿ mod a_n=0)

=>(a mod a₁=0) /\ (a mod a₂ = 0) /\ (a mod a₃=0) /\ …/\ (a mod a_n=0)

a nhỏ nhất chính là tích của a₁,a₂,…,a_n.

Từ đó ta xét với N^N = aⁿ.

N nhỏ nhất chính là N=a₁ x a₂ x a₃ x … x a_n.

Đây mới chỉ là điều kiện cần, điều kiện đủ là cần phải có N lớn hơn hoặc bằng số mũ lớn nhất của các thừa số nguyên tố của A, chính là max{b_n}.

Từ đây ta hình thành thuật toán:

Bởi đề bài yêu cầu chỉ cần tính N nhỏ nhất ta chỉ cần lưu tích của các thừa số nguyên tố của A, sau đó là kiểm tra xem N có lớn hơn hoặc bằng  max {b_n}, nếu không thì nhân N với số nguyên dương nhỏ nhất khác 1 là số 2, nếu vẫn chưa được thì nhân tiếp với 3… dừng đến khi N lớn hơn

max{b_n}.Nhưng còn 1 trường hợp là số nhân tiếp có thừa số nguyên tố có số mũ lớn nhất.Trường hợp này ta phải phân tích nó ra xem thử số mũ của thừa số nguyên tố ấy ứng với nó là bao nhiêu,gọi là k.Cụ thể là giá trị để N so sánh sẽ không còn là max{b_n} mà sẽ giảm đi (k+1) lần.

Trong trường hợp có nhiều thừa số có cùng số mũ lớn nhất của A thì chỉ lấy số nhỏ nhất bởi chỉ cần nhân N với hợp số của số nhỏ nhất cũng đủ rồi bởi A  ≤ 10⁹.

VD: Với trường hợp đơn giản nhất là N=2x3x4.

N^N=(2 x 3 x 4)^{2 x 3x4} >>10⁹.

Các bạn muốn trường hợp lớn hơn có thể dùng mảng để giải quyết hoàn toàn vấn đề còn lại.

Mã nguồn tham khảo:

#include <stdio.h> long minN(long a) {        long i,n=1;        int dem,max=0,max1;        for (i=2;a > 1;i++)        {               if (a % i ==0)               {                      for (dem =0;a % i == 0;a /= i,dem ++);                      if (dem > max)                      {                            max = dem;                            max1 =i;                      }                      n=i*n;               }        }        int j1,j = 2;        long max2;        while (n < max2)        {               max2=max;               j1=j;               for(dem=1;j1 % max1 ==0;j1 /= max1,dem++);               max2 /= dem;               n += n;               j++;        }        return n; }