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

Nhận định bài toán:

Yêu cầu bài toán tương đương:

x^x mod A =0 và X phải đạt giá  trị Min

thoạt nhìn ta nghĩ để chia hết cho A thì

X^x=A

ó X=log_xA          (1)

Từ đó ta giải hệ (1) ta được kết quả thỏa mãn x

Nhưng với nhận định trên ta không thể tìm được giá trị A Min để thỏa yêu cầu bài toán, hơn nữa,  trong lập trình không có chức năng slove như trên máy tính bỏ túi. Ta khó lòng tính được

Có cách đơn giản hơn chúng ta dùng vòng lặp for

Ta cho i chạy từ 1 đến A sao cho iⁱ mod A=0

Trường hợp A là số nguyên tố i sẽ chạy tới giá trị bằng A. Đồng thời khi tới giá trị nhỏ nhất ta dùng lệnh break để dừng lại,

Bài giải:

./*Code bai tap 1*/ #include<stdio.h> #include<conio.h> #include<math.h> void main() {        unsigned int a,i,x,n;        printf("nhap so nguyen tu nhien A: "); scanf("%d",&a); /*khai bao phan tu A*/        for(i=1;i<=a;i++)// tao vong lap        {               n= float(pow(float (i),int (i) ));               if(n%a==0)               {                      x=i;break;// ngung vong khi tim duoc gia tri i Min               }        }        printf("gia tri can tim cua X la: %d",x);        getch(); }

Nhưng thực sự kết quả chạy chỉ đúng được khi A có giá trị nhỏ, với những A có giá trị lớn thì kết quả X luôn bằng 16.

Vì vậy ta phải giải quyết vấn đề theo hướng khác

Bây giờ ta tách A ra bằng tích các thừa số nguyên tố, khi đó A có  dạng: A=a*b*c*d*e…. với a,b,c,d,e … là những số nguyên tố

Từ kết quả tách trên ta lấy tích của các số nguyên tố lại với số mũ lớn nhất ta được kết quả

Bài giải:

#include<stdio.h> #include<conio.h> void main() {        unsigned long max, n,i,b,s;        printf("nhap vao gia tri cua so nguyen n: "); scanf("%lu",&n);        s=1;max=0;i=1;        for(i=2;i<=n;i++)        {               b=0;               if(n%i==0)               {                      s=s*i;                      while(n%i==0)                      {                            b++;                            n=n/i;                      }                      if(b>max)                      {                            max=b;                      }               }        }        if(s<=max)        {               s=s*2;        }        printf("gia tri can tim la: %lu",s);        getch(); }

Với thuật toán này ta có thể rút ngắn được thời gian hơn rất nhiều cho vong lặp, và hạn chế được việc tràn số như trường hợp nêu trên.