Bài toán số học N mũ N chia hết cho A bất kỳ

Bài 1: Cho số tự nhiên A. Tìm số tự nhiên N nhỏ nhất sao cho N^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ị từ 1 đến 10⁹ .
Ví dụ:  Nhập A=8, xuất ra N=4.
           Nhập A=13, xuất ra N=13.
     
Hướng giải quyết:

Vì N^N chia hết cho A nên N^N chia hết cho tất cả các ước nguyên tố của A. Suy ra N chia hết cho tất cả các ước nguyên tố của A. 

Nếu phân tích A ra thừa số nguyên tố A = p[1]^e[1] .p[2]^e[2].p[3]^e[3].p[4]^e[4]...........p[k]^e[k]  thì N có dạng N = p[1]^t[1] .p[2]^t[2].p[3]^t[3].p[4]^t[4]...........p[k]^t[k] .

Suy ra:

N^N = p[1]^t[1].N .p[2]^t[2].N.p[3]^t[3].N.p[4]^t[4].N...........p[k]^t[k].N chia hết cho A khi và chỉ khi với với ∀i∈(1,k), t[i].N ≥ e[i].

Suy ra:

N ≥ e[i]/t[i], lúc này để tìm N ta chỉ cần duyệt với các giá trị t[i] trong khoảng từ 1 đến e[i].

     Để rút ngắn quá trình duyệt ta có thể dựa vào một số nhận xét sau:

1.   Vì A ≤ 10⁹ ≤ 2³⁰ và  N = p[1]^t[1] .p[2]^t[2].....p[k]^t[k] nên  với N ≥ 30 thì N^N nhất định sẽ chia hết cho A. Trường hợp A có hơn 2 ước nguyên tố thì N ≥ 2x3x5=30. Vậy số N nhỏ nhất cần tìm trong trường hợp này là: N=p[1].p[2]......p[k].
2. Nếu A có ít hơn 2 ước nguyên tố tức là chỉ có 1: A=p[1]^e[1] thì số N nhỏ nhất phải tìm là N = p[1]^t[1] với t[1] nhỏ nhất thỏa t[1].N = t[1].p[1].p[1]^t[1]-1 ≥ e[1] ⇒ t[1].p[1] ≥ e[1]   ⇒ Min t[1] = [e[1]/p[1]] + 1 (phần nguyên của e[1]/p[1] +1) hay t[1] = ceil(e[1]/p[1]).
3. Nếu A có đúng 2 ước nguyên tố thì ta dùng vòng lặp để xét duyệt tìm N. 

Soure Code (C/C++):

#include<stdio.h>
#include<math.h>
int ktnt(int x)
{ 
    int d=0;
    for(int j=1;j<=x;j++)
    {
        if(x%j==0)
        {
            d++;
        }
    }
    if(d==2) return 1;
    else return 0;
}
int main()
{
    int a,b,p[100],e[100],k;
    double t,n;
    printf("Nhap A ");
    scanf("%d",&a);
    b=a;
    k=0;
    for(int i=2;i<=a;i++)
    {
        if (ktnt(i)&&(b%i==0))
        {
            k++;
            p[k]=i;
        }
    }
    for(int i=1;i<=k;i++)
    {
        e[i]=0;
        while(b%p[i]==0)
        {
            e[i]++;
            b=b/p[i];
        }
    }
    if (k==1)
    {
        t= ceil((double)e[1]/p[1]);
        n = pow((double)p[1],t);
        printf("N = %.0f\n",n);
    }
    if (k>=3)
    {
        n=1;
        for(int i=1;i<=k;i++)
        {
            n*=p[i];
        }
        printf("N = %.0f\n",n);
    }
    if (k==2)
    {
        n=a;
        for (int t1 = 1, pp1 = p[1]; t1 <= e[1]; ++t1, pp1 *= p[1])
          for (int t2 = 1, m = pp1 * p[2]; t2 <= e[2]; ++t2, m *= p[2])
             if (m * t1 >= e[1] && m * t2 >= e[2])
                if (m < n) n = m;
         printf("N = %.0f\n",n);
    }
    return 0;
}
 

Bài 2: Xem công thức tính sau đây (đề thi tuyển sinh cao học ngành KHMT, năm 2011): 

Trong đó Max, Min lần lượt là giá trị lớn nhất, nhỏ nhất của n số thực (được nhập vào từ
thiết bị nhập chuẩn) a0, a1, …, an-1. 
Chỉ dùng duy nhất 1 vòng lặp (for hoặc while), đề xuất cách thức để nhập n số thực như
trên  và  tính  giá  trị  của  biểu  thức  Aver,  xuất  kết  quả  tính  ra  thiết  bị  xuất  chuẩn.  Viết chương trình để minh họa đề xuất đó. 

Lưu ý: Phần này sinh viên chưa học về mảng, như vậy vấn đề chính của bài toán này là
không thể dùng mảng để lưu giá trị của n số thực nói trên. Như vậy phải đề xuất một giải
pháp “thông minh” để nhập và tính toán mà không đưa trước các số thực này vào mảng.

Hướng giải quyết:

Vì chưa học về mảng nên ta không thể tính Aver bằng công thức như trong đề bài mà phải biến đổi:

Lúc này, ta có thể dễ dàng tính được A, B và tìm được Max, Min trong quá trình nhập a_i .

Soure Code (C/C++):

#include<stdio.h>
#include<math.h>
int main()
{
    float a,max,min,A=0,B=0,aver;
    int n,i=1;
    printf("Nhap n ");
    scanf("%d",&n);
    while(i<=n)
    {
        printf("Nhap so thuc thu %d ",i);
        scanf("%f",&a);
        if(i==1)
        {
            max=min=a;
        }
        else
        {
            if(max<a) max=a;
            if(min>a) min=a;
        }
        A+=a*a;
        B+=a;
        i++;
    }
    aver=2*A-2*(max+min)*B+pow(max,2)+pow(min,2)+(float)n/2*pow((max-min),2);
    printf("Aver = %f ",aver);   
}