Hướng dẫn giải Bài 1 trong BT nghiên cứu :)

[Problem]

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^9.
Ví dụ:
Số nhập vào là A          Số xuất ra là N
8                                       4
13                                     13

[Solution]

Lần đầu tiên nhìn vào bài toán, nhiều bạn có thể tròn mắt nói rằng: số gì mà lớn vậy kiểu nào chứa nổi trời? Đúng thật, nếu nhìn ban đầu thì có lẽ chúng ta phải bó tay trước bài toán này. Nhưng nếu biết khóe léo vận dụng vài kiến thức của số học + vài nhận xét thì bạn có thể giải bài toán một cách nhẹ nhàng.
Trước hết quan sát trằng để N^N chia hết cho A, thì N phải chia hết cho các ước nguyên tố của A.
Mặt khác, nếu viết:
A= pr[1]^e[1]  *  pr[2]^e[2]  *  …  *  pr[k]^e[k];
Như vậy, với mỗi pr[.] cần xuất hiện ít nhất một lần trong N, nghĩa là N= pr[1]^t1 * pr[2]^t2 * … * pr[k]^tk, với ti>=1

Bước 1: Phân tích A ra tích các thừa số nguyên tố và số mũ của nó. Việc này có thể thực hiện nhanh chóng bằng sàng Eratosthenes, lưu ý các bạn không nên cài 1 hàm kiểm tra số nguyên tố và kiểm tra từng số nguyên tố từ 2 tới round(sqrt(A)) như vậy sẽ rất mất thời gian!

Bước 2: Ta xét các trường hợp cụ thể sau:
Trường Hợp 1 – A chỉ có 1 ước số nguyên tố:
Lúc này A=pr[1]^e[1], cần tìm N= pr[1]^x;
x sẽ chạy giá trị từ 1 tới ceil(e[1] / pr[1]) Cho đến khi x*pr[1]^x >= e[1] thì dừng, Lúc này N= pr[1]^x;

Trường Hợp 2 – A chỉ có 2 ước số nguyên tố:
Ta dùng 2 vòng lặp for lồng nhau để tìm ra N

kq = n;

for (int t1 = 1, temp1 = pr[1]; t1 <= e[1]; ++t1, temp1 *= pr[1])

for (int t2 = 1, temp = temp1 * pr[2]; t2 <= e[2]; ++t2, temp *= pr[2])

if (temp * t1 >= e[1] && temp * t2 >= e[2])

if (temp < kq) kq = temp;

Trường Hợp 3 – A có từ 3 ước nguyên tố trở lên:
Ta có 1 số nhận xét sau:
Do A <= 10^9 < 2^30 do đó khi N có 3 ước nguyên tố trở lên N >= pr[1]*pr[2]*pr[3] >= 2*3*5=30
mà với giới hạn đó thì số mũ tối đa của một cơ số (cụ thể là 2) không thể vượt quả 30. Vì vậy trong trường hợp này, giả dụ A có k ước nguyên tố N = pr[1] * pr[2] * … * pr[k].
Đến đây bài toán đã được giải quyết xong! 🙂
Bonus: Nói vậy thôi, bài này chủ yếu là dựa vào Google + chịu khó đọc hiểu bài giải có sẵn là có thể làm được, hihi :D!

[Code]

#include <stdio.h>

#include <string.h>

#include <conio.h>

#define lim 50000



bool a[lim];

int pr[lim/2], e[lim/2];

void SanNgTo(void)

{

     memset(a,true,sizeof(a));

     int i,j;

     i = 1;

     a[1]=false;

     while (i*i<=lim){

           while (!a[i]) i++;
           j=2;

           while (j*i<=lim){
                 a[j*i]=false;

                 j++;

           }

           i++;

     }

 }

void PhanTich(int n, int& k)

{

    int i=1;
    k=0;

    while (n!=1){

          while (!a[i]) i++;

          if (n%i==0){

             k++;

             pr[k]=i;
             e[k]=0;

          }

          while (n%i==0){
                e[k]++;

                n/=i;

          }

          i++;

    }

}

int Solve(int k, int n)

{

    int kq;

    switch (k){

           case 1:

                int t;

                t=e[1]/pr[1];

                if (e[1]%pr[1]!=0) t++;
                kq=1;

                for (int i=1; i<=t; i++)

                {

                    kq*=pr[1];

                    if (kq*i>=e[1]) break;

                }

                break;

           case 2:

                int temp1, temp;

                kq = n;

                for (int t1 = 1, temp1 = pr[1]; t1 <= e[1]; ++t1, temp1 *= pr[1])

                    for (int t2 = 1, temp = temp1 * pr[2]; t2 <= e[2]; ++t2, temp *= pr[2])

                         if (temp * t1 >= e[1] && temp * t2 >= e[2])

                             if (temp < kq) kq = temp;

                break;

           default:

                kq=1;

                for (int i=1;i<=k;i++)

                    kq*=pr[i];

    }

    return kq;

}

int main(void)

{

    SanNgTo();

    int n, a, k=1;

    printf(“Nhap A= “);
    scanf(“%d”,&a);

    PhanTich(a,k);

    n = Solve(k,a);
    printf(“So N nho nhat can tim: %d\n”,n);

    printf(“va %d^%d chia het cho %d\n”,n,n,a);
    getch();

}

Download Source Code (*.CPP)

Sàng Eratosthenes

Thuật toán sàng nguyên tố Eratosthenes là một công cụ mạnh mẽ để giải quyết những bài toán đòi hỏi phải kiểm tra số nguyên tố nhiều lần. Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố.

Thuật toán:
Dùng 1 mảng bool có N phần tử, với giá trị khởi tạo cho các phần tử của mảng đều là True, với ý nghĩa các số từ 1..N đều là số nguyên tố.
Gán a[1]=false (1 không phải là số nguyên tố);
B1: i++ cho đến khi a[i]= true;
B2: Điền các phần tử của mảng a có chỉ số là 2*i, 3*i… là false (với ý nghĩa các số này ko phải là số nguyên tố)
B3:Nếu i*i>=N thoát chương trình, nếu không quay lại bước 1.

pseudocode:

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., while i ≤ n/2:
  if A[i] is true:
    for j = 2i, 3i, 4i, ..., while j ≤ n:
      A[j] = false

Now all i such that A[i] is true are prime.

Ngoài ra bạn có thê tham khảo công cụ mạnh hơn (nhưng cài đặt cũng phức tạp hơn) đó là sàng Atkin.

Hướng dẫn giải Bài 2 trong BT nghiên cứu :)

[Problem]

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.

[Solution]

Nếu như không có yêu cầu cuối cùng (chỉ dùng 1 vòng lặp và không dùng mảng) thì bài toán có lẽ đã đơn giản hơn nhiều. Ý tưởng để giải bài toán này là xét xem liệu biểu thức Aver có thể được tính sau khi đã kết thúc quá trình nhập hay không?
Đầu tiên ta xét tổng:

Nếu ta khai triển (ai-Max)^2 bằng hẳng đẳng thức đáng nhớ học hồi cấp II 😛 ta được: ai^2 – 2*ai*Max + Max^2. Lúc này ta sẽ có:

1. a0^2 + a1^2 + a2^2+  … + a(n-1)^2
2. n*Max^2
3. -2*Max*Sum,
   với  Sum  = a0 + a1 + a2 + … + a(n-1) <- Cái này có thể tính dễ dàng

Như vậy nhìn cái tổng có vẻ rắc rối trên bằng với: (1) + (2) + (3).
Đến đây mọi chuyện đã có vẻ khá rõ ràng. Vừa nhập vừa tính Sum và cập nhật Max, Min. Kết thúc quá trình nhập kết tất cả lại theo cách tính được nêu ra ở trên (!) 🙂

[Code]

#include <stdio.h>

#include <conio.h>

main()

{

      float min, max, Aver, sum, sumbp, a;

      int n;

      printf(“Nhap n = “);

      scanf(“%d”,&n);
      printf(“Nhap a0 = “);

      scanf(“%f”,&a);

      max = a;
      min = a;

      sum = a;

      sumbp = a*a;

      for (int i=1; i<=n–1; i++){
          printf(“Nhap a%d = “,i);

          scanf(“%f”,&a);

          if (min>a) min=a;

          if (max<a) max=a;

          sum+=a;
          sumbp+=a*a;

      }

      Aver= n*max*max + n*min*min + 2*sumbp – 2*max*sum – 2*min*sum + (float)n/2*(max–min)*(max–min);
      printf(“Aver = %f\n”,Aver);

      getch();

}

Download Source Code (*.CPP)

Hello world!

#include <stdio.h>

main()

{

        printf(“Hello WordPress :)!“);

}