Bài toán đếm số bộ nghiêm nguyên thỏa mãn

#1

Mọi người giúp e bài này với, e hơi bị ngu toán nên nghĩ mãi chẳng ra hướng giải tổng quát của nó ạ:
Cho phương trình nghiệm nguyên không âm ax+ by+cz=t. Tìm số bộ nghiệm x, y, z thỏa mãn phương trình.
INPUT: 4 số a, b, c, t;0<=a, b, c, t<=100.
OUTPUT:
Số bộ nghiệm khác nhau thỏa mãn. Chú ý (1, 2, 3) và (3, 2, 1) là 2 bộ nghiệm khác nhau. In ra 0 nếu có vô số nghiệm.( Trường hợp pt vô nghiệm in ra 0 nốt).

#2

Chạy trâu chắc ko sao :smiley:

3 Likes
#3

Chạy trâu bị tle ạnh ạ

#4

Giải như này thì có người sẽ không cho rằng đây là chạy trâu :slight_smile: giờ chạy x từ 0 lên, rồi chạy y từ 0 lên, z thì trừ ra :smiley:

5 Likes
#5

Nghe cũng được đó ạ, nhưng mà “z thì trừ ra” là sao vậy???

#6

Thay vì lặp cả z từ 0 thì lấy t - (ax + by) => cz.

3 Likes
#7

làm sao chứng minh nó có vô số nghiệm nhỉ ?
nếu a hoặc b hoặc c = 0 ah ?_?
chạy thử bằng python

def solve(a, b, c, t):
    result = []
    if a==0 or b==0 or c==0:
        return 0
    for y in range(0, 101):
        for z in range(0, 101):
            ax = t-b*y - c*z
            if ax>=0 and ax%a == 0:
                result.append((int(ax/a), y, z))
    return result if result else 0
2 Likes
#8

^ bài này đếm thôi mà :slight_smile:

# pseudo
-> a, b, c, t

<- 0 if 0 in [a, b, c]
swap(a, b) if a < b
swap(a, c) if a < c
swap(b, c) if b < c
# brute
count := 0
for x := 0 to t STEP a do
  for y := 0 to t - x STEP b do
    count += 1 if (t - x - y) % c == 0

<- count
5 Likes
#9

Nà ní???

#10

chạy trâu thôi, không âm, t <= 100, thì x, y, z cũng 100 là max, chạy trâu qua 100^3 = 10^6 TLE kiểu gì

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