Bài tập nghiên cứu lần 1

Bài toán 1:

Cho số tự nhiên A. Hãy tìm số tự nhiên  N nhỏ nhất sao cho {N^N} chia hết cho A  . Trong đó  có giá trị trong khoảng  [1, {10^9}].

Ý tưởng 

Số b chia hết cho a khi và chỉ khi lũy thừa các số nguyên tố trong phân tích của b không nhỏ hơn trong phân tích của a. Như vậy ta để tìm số N điều đầu tiên cần làm là phân tích A  ra số nguyên tố:

A = a_1^{k_2}a_2^{k_2}...a_n^{k_n}

Chắc chắn một điều  số  ta cần tìm là bội của các số a_1, ta lấy tích N_0 = a_1a_2...a_n,  và sao sánh N_0 với lũy thừa của các ước  trong  phân tích của A.

  • Nếu  N_0 \ge max_{i=1..n}(k_i) ta chọn N = N_0.
  • Ngược lại, ta nhân N_0   với  các số tự nhiên  tăng dần (2, 3, …) cho đến khi  N_0 thỏa mãn tính chất trên. Đến đây nảy sinh vấn đề nếu thừa số nhân vào  cũng là ước hay chia hết cho ước của A thì sao?  Khi đó ta phải tăng lũy thừa của  trong  lên trong quá trình kiểm tra.
    vis du: A = 8 = 2^3 \Rightarrow N_0 = 2\ do\ N_0 < max_{i=1..n}(k_i) = 2 \Rightarrow N = N_0\times2 = 4 . Kiểm tra thấy N = 4 thỏa. Kết thúc quá trình.

Code

//BT NMCNTT - Tim so n nho nhat thoa n^n chia het cho so A cho truoc
#include<stdio.h>
#include<math.h>
//Ham kiem tra so nguyen to
int kt_nguyento(int n)
{
    int i, dem=0;
    for (i=2;i<=sqrt(n);i++)
    {
        if (n%i == 0) dem++;        
    };
    if (dem==0) return 1;
    else return 0;    
};
//Ham phan tich ra thua so nguyen to
void uoc_so(unsigned int A, int *uoc, int *so_mu, int &temp1)
{
    unsigned int a, temp2, j;
    temp1=0;
    a=A;
    for (j=2;a>1;j++)
    {
        if (kt_nguyento(j))
             if ((a%j)==0)
            {
                temp1++;
                uoc[temp1]=j;
                temp2=0;
                while (a%j==0)
                {
                    a=a/j;
                    temp2++;
                };
                so_mu[temp1]=temp2;
            };
    };
};
//Ham kiem tra su trung lap uoc nguyen to
void kt_uoc(int m, int temp1, int *uoc, int *so_mu_2)
{    
    int i;
    for (i=1; i<=temp1; i++ )
    {
        while ((m%uoc[i])==0)
        {
            so_mu_2[i]=so_mu_2[i]+1;
            m =(m/(uoc[i]));
        };
    };
};
//Ham kiem tra n thoa yeu cau chua
int kt_yeucau(unsigned int n, int temp1, int *so_mu, int *so_mu_2)
{
    int i;
    for (i=1; i<=temp1; i++ )
    {
        if ((n*so_mu_2[i])<so_mu[i])
        {
            break;
        };
    };
    if (i== (temp1+1)) return 0;
    else return 1;
};
//Chuong trinh chinh
int main()
{
    unsigned int A, n;
    int m, uoc[100], so_mu[100], so_mu_2[100], temp1, k;
    char thu;
    do
    {
        printf("A = ");
        scanf("%u",&A);    
        uoc_so(A, &uoc[0], &so_mu[0], temp1);
        n=1;
        printf("%u = ",A);
        for (k=1;k<=temp1;k++)
        {
            printf("(%d^%d)",uoc[k],so_mu[k]);
            n*=uoc[k];
            so_mu_2[k]=1;
        }; //In ra phan ticb nguyen to cua so A
        m=1;
        while (kt_yeucau((n*m), temp1, &so_mu[0], &so_mu_2[0]))
        {        
            m++;
            for (k=1; k<=temp1; k++)
            {
                so_mu_2[k]=1;
            };
            kt_uoc(m, temp1, &uoc[0], &so_mu_2[0]);                
        };
        printf("\nSo nho nhat thoa yeu cau la %u\n",(n*m));
        printf("Again? (Press y to try again or any other key to stop) ");
        fflush(stdin);
        scanf("%c",&thu);
    }while((thu=='y') || (thu =='Y'));
    return 0;
};

Tiếp tục đọc

Advertisements