BÀI 1 – Đồ Án NMCNTT1

ĐỀ BÀI

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

BÀI GIẢI + SUY LUẬN

Trước tiên, ta có 1 nhận xét nho nhỏ: bài toán này không thể nào cho một biến i chạy từ 1 đến A rồi kiểm tra lần lượt xem {{i}^{i}} có chia hết cho A hay không được. Vì vậy ta cần một hướng đi khác để giải quyết.

Ta để ý rằng, nếu A có dạng: A=x_{1}^{{{y}_{1}}}x_{2}^{{{y}_{2}}}x_{3}^{{{y}_{3}}}...x_{k}^{{{y}_{k}}} thì giá trị N cần tìm phải có dạng: N=x_{1}^{{{z}_{1}}}x_{2}^{{{z}_{2}}}x_{3}^{{{z}_{3}}}...x_{k}^{{{z}_{k}}}. Tới đây ta chia làm 2 trường hợp như sau (nếu chính xác phải là 3 trường hợp nhưng vì trình độ còn hạn chế nên chỉ chia làm 2 trường hợp):

– Trường hợp 1: A chỉ có 1 ước nguyên tố duy nhất, tức A có dạng: A={{x}^{y}} với x là số nguyên tố. Khi đó để tìm N, ta tìm 1 số m sao cho m là số nguyên bé nhất \ge \frac{y}{x}. Từ đây giá trị N sẽ là: N={{x}^{m}} (tuy nhiên, khi y càng lớn thì có thể thuật toán cho trường hợp 1 sẽ sai)

– Trường hợp 2: A có từ 2 ước nguyên tố trở lên, tức A có dạng như ban đầu thì số N nhỏ nhất cần tìm sẽ là: N={{x}_{1}}{{x}_{2}}{{x}_{3}}...{{x}_{k}} (nếu nói chính xác thì chỉ đúng đối với số A có từ 3 ước nguyên tố trở lên, còn khi số ước nguyên tố bằng 2 thì phải dùng 1 thuật toán phụ để giải quyết)

MÃ NGUỒN

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

void main()
{
/* công dụng của các biến:
d: đếm số ước của i
d2: đếm số ước nguyên tố của a
d3: lũy thừa của số p trong phân tích a = p^d3 trong trường hợp a chỉ có 1 ước nguyên tố duy nhất
m1: kết quả cần tìm trong trường hợp số ước nguyên tố từ 2 trở đi
m2: số nguyên bé nhất >= x */
int d=0, d2=0, d3=0, m1=1, x, m2;
long a, b;
printf(“Nhap a: “);
scanf(“%d”, &a);
b = a;
for (int i=1; i<=a; i++)
{
if (a%i==0)
{
for (int j=1; j<=i; j++)
if (i%j == 0) d++;
}
if (d==2)
{
x=i;
while (b!=1)
{
b=b/i;
d3++;
}
m1 = m1*i;
d2++;
}
d=0;
}
if (d2 >= 2) printf(“Gia tri n: %d\n”, m1);
if (d2 == 1)
{
if (d3%x == 0)
m2 = d3/x;
else
m2 = int(d3/x)+1;
printf(“Gia tri n: %.0lf\n”, pow(double(x), double(m2)));
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s