PDA

View Full Version : Factorization



guardian
12-02-2003, 16:56
Factorization
Problem Description
Any positive integer n (n>1) can be expressed as a product of a set of positive integers that are greater than 1, e.g., 24 = 3 * 8. Usually there is more than just one set, e.g., 24 = 4 * 6 = 2 * 12 = 2 * 2 * 6. So {4, 6}, {2, 12}, and {2, 2, 6} are another three sets. The order of elements in the set does not matter, so {2, 2, 6} is considered the same as {2, 6, 2}. (Note set is different from mathematical definition of set, as we can have duplicated items). Of course {24} is another set whose product equals to 24. Let's define a function f over all positive integer as:

f(n) = the number of different ways to factorize a integer n , if n>1
f(1) = 1

f(24) will yield 7 as there are 7 such sets: {2, 2, 2, 3}, {2, 2, 6}, {2, 4, 3}, {2, 12}, {3, 8}, {4, 6}, and {24}

Given an interval [i...j], try to find an integer n with the biggest f(n).

Input
The input consists of a few lines. Each line has two integers, i and j. They are separated by a single space. No input exceeds 1,000,000.

Output
For every line of input, print two integers n and m on one line, separated by one single space, where:

i≤n≤j, m = f(n), and n = the number that has largest number of factorizations.

If there are more than one such n, output the smallest one.

Sample Input
60 70
1000 2000
2000 3000
3000 4000
4000 5000
5000 6000
6000 7000
7000 8000
8000 9000
9000 10000

Sample Output
60 11
1440 171
2880 289
3600 269
4320 382
5760 467
6720 426
7200 484
8640 662
9600 467

Required Time : For each input, running time is not exceed 5s
-----------------------------------------------------

Bài này thì thuật toán tìm số cách factorize ra không khó, nhưng để chạy từ 1 đến 1.000.000 thì :confused:. Các bác giúp em với, đây là bài em cần nộp (thứ hai tuần sau hết hạn) :.(

guardian
13-02-2003, 18:51
Hix, sao không có ai reply hết zậy, hỗng lẽ nhát đọc english sao :D, hay là too tough.

skywalker
14-02-2003, 20:56
nghe có vẻ như bác học ở LHP, nhưng mà bài này chạy trên free pascal phai ko, đó là yếu tố quyết định đó :D

guardian
14-02-2003, 21:03
Bài viết được gửi bởi skywalker
nghe có vẻ như bác học ở LHP, nhưng mà bài này chạy trên free pascal phai ko, đó là yếu tố quyết định đó :D
Rất tiếc đó không phải là vấn đề :confused: Hix, đợi các bác lâu wé, em giải xong rồi còn đâu lol :cool: , mod xoá bài thread này giùm em nhé.
P.S: chính xác là em tìm ra lời giải, nghĩ nhiều ngày rồi mà không ra, cuối cùng nhờ đến Net và ...... hhehehhe :D

haison3000
15-02-2003, 07:58
Bài này cũng rất hay! Bạn tìm được lời giải thế nào? Mình suy nghĩ mãi mà chưa ra.....

khôngtên
16-02-2003, 17:49
Bác có thể post bài dịch cho anh em đi chứ cứ ín lịt thì.... ! Bác post bài dịch nhé !

guardian
16-02-2003, 20:48
Hix, đến bài này mà bạn cũng bắt dịch ra, thế sao bạn đọc ebook nổi hở khôngtên :D.
Mình có attach theo code của bài này (viết trong java), bạn nào không biết java thì thông cảm vậy nhé ;)

Junior IT
16-02-2003, 22:58
Sao ko thấy file attach??
Bạn tìm được đề bài này từ đâu?

guardian
16-02-2003, 23:06
Hả, sao lạ thế, chắc server bị gì rồi, để mình upload lại.
To JuniorIT: cái đề này là bài tập của mình, chứ kiếm đâu mà kiếm :D ;)
Hix, ra là kô cho upload java, nhảm thật. :(

haison3000
17-02-2003, 00:08
Vậy thì nói sơ qua thuật toán là anh em bít rùi.

guardian
17-02-2003, 00:13
F[1] = 1;
for (int i = 2; i <= limit; i++) {
int max = limit / i;
for (int j = 1; j <= max ; j++)
if (F[j] > 0)
F[i * j] += F[j];
}
Limit ở đây là số lớn nhất của range (i.e here is 1000000)

Try to print out F, and see what's inside F :)

P.S: sao người hỏi lại trở thành người trả lời thế này :cool: :rolleyes: :D

skywalker
27-02-2003, 05:20
em cũng có nghe nói đề rồi, nhưng mà nếu viết bằng pascal thì phải chạy trên free với bộ nhớ lớn chứ

haison3000
06-03-2003, 10:55
BÀi này QHD rất hay. Công thức QHD cũng không phải dễ mà nghĩ ra dc.
Bây giờ biết công thức rồi có ai cm đc không?

guardian
07-03-2003, 16:34
Chứng minh hơi trừu tượng một tí. Thật ra kô phải chứng minh mà là understand lol , cái algo này dựa trên sàng eurothetense (kô biết ghi đúng kô :rolleyes: )

haison3000
08-03-2003, 01:11
VẬy thì bạn trình bày hơi trừu tượng thử xem.
Chúng ta cùng trao đổi thêm.

monkeyvu
05-05-2003, 08:28
Don't talk English in this gum.