Đề 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\le A\le {{10}^{9}}

Ví dụ :

Số nhập vào là A :                                Số xuất ra là N :

8                                                                   4

13                                                                13

Advertisements

Thuật toán 1

 

Việc đầu tiên là phân tích n thành tích các thừa số nguyên tố :

A=\prod\limits_{i=1}^{k}{{{a}_{i}}^{{{b}_{i}}}}

Đặt :     {{a}_{0}}=\prod\limits_{i=1}^{k}{{{a}_{i}}}

{{b}_{m\text{ax}}}=m\text{ax(}{{\text{b}}_{i}})\Rightarrow {{a}_{m\text{ax}}}

Ở đây có 2 trường hợp :

                      TH1 : {{a}_{0}}\ge {{b}_{m\text{ax}}}\Rightarrow N={{a}_{0}}

                      TH2 : {{a}_{0}}<{{b}_{m\text{ax}}}\Rightarrow  cho chạy x đến khi biểu thức sau thỏa :

(x+1)({{a}_{0}}.a_{m\text{ax}}^{x})\ge {{b}_{m\text{ax}}}

Khi đó : N={{a}_{0}}.a_{m\text{ax}}^{x}

Ví dụ :

A=32\Rightarrow A={{2}^{5}}

{{a}_{0}}=2;{{a}_{m\text{ax}}}=2;{{b}_{m\text{ax}}}=5

Tính toán ta được : x=1\Rightarrow N={{2.2}^{1}}=4

Vậy {{4}^{4}} là số nhỏ nhất chia hết cho 32 thỏa yêu cầu.

Code 1

 

#include <stdio.h>
#include <conio.h>
#include <math.h>

int ktnt(long x);

void phantich(long x, long &maxa, long &maxb, long &tich);

void main()
{
long n, a, x, maxa, maxb, tich;

printf(“Nhap A : “);
scanf(“%ld”, &a);
phantich(a, maxa, maxb, tich);
if (tich >= maxb) {
n = tich;
}
if (tich < maxb) {
x = 0;
while ((x+1)*(tich*pow(double(maxa), double(x))) < maxb) {
x++;
}
n = tich*pow(double(maxa), double(x));
}
printf(“So N thoa man : %ld”, n);
getch();
}

int ktnt(long x)
{
int i;

if (x < 2) {
return 0;
}
if ((x >= 2) && (x <= 3)) {
return 1;
}
if (x >= 4) {
for (i = 2; i <= sqrt((double)x); i++) {
if (x % i == 0) {
return 0;
}
}
}
return 1;
}

void phantich(long x, long &maxa, long &maxb, long &tich)
{
int i, dem;

maxa = 0;
maxb = 0;
tich = 1;
for (i = 2; i <= x; i++) {
if (ktnt(i) == 1) {
dem = 0;
if (x % i == 0) {
tich = tich*i;
}
while (x % i == 0) {
dem++;
x = x/i;
}
if (dem > maxb) {
maxb = dem;
maxa = i;
}
}
}
}