Kiểm tra chia hết mà không so sánh

#1

Input

  • Hai số nguyên dương a và b
    0 < a, b < 1000

Output

  • 0, nếu a không chia hết cho b
  • 1, nếu a chia hết cho b

ví dụ

  • Input 21 7
  • Output: 1

mọi người giúp em làm theo phép dịch bit với ạ, em định dùng dịch bit để xét bit dấu mà mãi không ra :((

1 Like
Thao tác với bit
#2

:sweat:

Sao cậu lại cần phép dịch bit thay vì check (a % b == 0)? :sweat_smile:
Và cậu đã thử xét bit dấu như thế nào rồi? Cho tớ coi code được không? :sweat_smile:

8 Likes
#3

dạ ý em định xét (a%b) -1 nếu chia hết thì nó sẽ mang dấu âm dịch bit thì sẽ ra 1 rồi lật bit ạ . còn nếu dư thì nó sẽ dương khi dịch bit ra 0 . em nghĩ thế nhưng code nó toàn lỗi ạ :sweat_smile:

1 Like
#4

Nhiều khi nhìn code dịch bit cũng k hiểu. Hình như nó là dấu & hay sao ấy

#5

& ở chỗ nào ạ :sweat_smile:

#6

Hở? :smile:
Ý tớ là, có vấn đề gì với code này không cậu? :smile:

    int a = 21, b = 7;

    if(a % b == 0) {
        printf("1\n");
    } else {
        printf("0\n");
    }
5 Likes
#7

Nếu làm thuần tuý bài này bằng bitwise thì bài này khá hay đấy chứ.

a, b < 1000 nên 1 số a, b không dài quá 10 bit. Ký hiệu b|a tức là a chia hết cho b.

Đặt a = 2^m \cdot x, b = 2^n \cdot y (m, n lẻ). Nhận thấy gcd(2^m, y) = gcd(2^n, x) = 1 nên muốn b|a thì 2^n | 2^m và y|x, suy ra m \ge n.

Với b \le 18 ta có bài toán Regular Expression for Binary Numbers Divisible by n - codewars.

Một số case đặc biệt:

  • Nếu b = 2^k - 1 \Rightarrow 2^{ik} \equiv 1\ \forall i

  • Nếu b = 2^k + 1 \Rightarrow 2^{2ik} \equiv 1,\ 2^{(2i+1)k} \equiv -1\ \forall i

6 Likes
#8

dạ ko vấn đề gì ạ … lúc đầu e hiểu sai là ko so sánh tức là ko đc dùng cả phép bằng luon :sweat_smile:

1 Like
#9

dạ em chưa hiểu ý anh lắm :sweat_smile:

#10

Mình đã nói ý gì đâu, mới bôi ra vài chữ thôi mà.

3 Likes
#11

nếu dùng đến bit thì anh có ý tưởng gì không cho em tham khảo với ạ

1 Like
#12

Không so sánh à ?

if(a % b){
    // không chia hết
}
else{
    // chia hết
}
5 Likes
#13

dạ em cảm ơn . em nhầm ạ :sweat_smile:

1 Like
#14

Đề yêu cầu không so sánh chứ đâu bảo dùng phép toán bit? Như cách @Duong_Act là chuẩn luôn rồi.

6 Likes
#15

Chấm online thì có danh sách các kí hiệu bị cấm chứ.

4 Likes
#16

Chủ thớt thử post đề lên xem đề có cấm những ký tự gì nào.

3 Likes
#17

Dạ em làm bài trong nhóm để luyện tập thôi nên cũng không có nói rõ cấm như nào ạ

#18 
while(a > b) a -= b
print(!a)

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