[Chôm từ reddit] Số nguyên phức tạp #1

Mình lại có challenge cho các bạn đơi!!!(Định ra ngày tết nhưng dạo này bận rộn vì học hành quá).

Đề bài như sau:

Cho số A , tìm giá trị nhỏ nhất của B + C nếu B * C = A. Hãy nhớ rằng cả ba số A, B, C đều là số nguyên dương(Không được sử dụng một trong 3 số là số nguyên âm). Có thể sử dụng brute force để tim được giá trị thích hợp cho B va C. Bạn không thiết phải nhập các chữ số hơn 6 kí tự(Trừ khi bạn thích ra oai thì còn ok :wink:).

Ví dụ: In ra kết quả của số A = 12345 thì B + C = 838. Mình sẽ giải thích cặn kẽ hơn kết quả này:

có thể biểu diễn số nguyên dương A = 12345 như cái đề ban đầu mình cho là A = B * C thành tích 2 số BC như sau:

12345 = 1 * 12345
12345 = 3 * 4115
12345 = 5 * 2469
12345 = 15 * 823

Tổng của các thừa số như sau:

112345 => 1+12345 = 12346
3
4115 => 3+4155 = 4158
52469 => 5+2469 = 2474
15
823 => 15+823 = 838

Vậy giá trị nhỏ nhất của B + C trong trường hợp này là: 838

VD2: Cho các số và kết quả như sau:

12 => 7
456 => 43
4567 => 4568
12345 => 838

Kết quả như vậy vì:
12 = 3 * 4, 456 = 19 * 24, 4567 = 1 * 4567 và 12345 = 15 * 823

Luật:

  • Sử dụng mọi ngôn ngữ, mọi chiều trò,…
  • Được phép dùng hàm, thư viện có sẵn
  • Khuyến khích phân tích code và chia sẻ thư viện. Code càng dài càng bá đạo thì game sẽ vui hơn

Gợi ý:

  • Phân tích số đó thành tích của các số nguyên tố. Sau đó công chúng lại

Chúc các bạn code vui vẻ!

Notice: Series “Số nguyên phức tạp” có tận #3 challenge hoặc nhiều hơn cơ!

1 Like

Challenge này dễ quá, Ara up 2 challenge còn lại đi :3

2 Likes

anh @noname00 cứ giải trước đi! Tí nữa em up lên

Bài 1 dùng [spoiler]Cauchy-Schwarz[/spoiler] :v

3 Likes

Có gì đâu phải sợ nhỉ ?

2 Likes

Mã giả:

X = 0
Lặp X không bằng 12345
— Nhập X
Kết thúc Lặp
In 838

Dùng chiêu trò nhé :joy:

3 Likes

:expressionless:

fn main(){
    let int = 5000usize;
    let mut b = (int as f64).sqrt() as usize;
    loop{
        if int % b == 0{
            println!("B + C = {}", b + int / b);
            break;
        } else{
            b = b - 1;
        }       
    }
}
3 Likes

Theo góc nhìn của toán học thì B+C nhỏ nhất khi B và C tiến đến gần căn bậc hai của A.

2 Likes

Vui tí

  • crawl data từ
"https://www.hackmath.net/en/calculator/divisors?n={}&submit=Calculate".format(n)
  • Lấy ra danh sách các ước: Lấy ra đoạn {list} có dạng
"Divisors of {n}: </b><br />{list}<br /><br />Input a positive integer and this calculator will calculate:<br>"
  • Xử lí data:

  • Nếu size của list lẻ, lấy ước giữa rồi bình phương ước đó lên.

  • Nếu size của list chẵn, lấy 2 ước ở giữa, rồi nhân 2 ước đó vào nhau.

EZ.

2 Likes

Rust :smiley:
Thử đi, vui lắm

3 Likes
2 Likes
var B = (int)System.Math.Sqrt(A);
while (A % B > 0)
    B -= 1;
return B + A / B;
3 Likes

Announcement: Tối nay ra số nguyên phức tạp #2 nhé mọi người

@drgnz, @noz1995, @noname00, @phamvandung, @hungaya, @rogp10, @Duong_Act

2 Likes

Có gì đó sai sai ở đây:

Uploading…

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?