2 số nguyên tố tương đương

#1

Chào mọi người. Mình đang tìm lời giải cho bài toán sau:

image
image975×299 43.3 KB

Mình có thử í tưởng của mình nhưng không hoạt động, mong mọi người xem và giúp mình với ạ. Mình đang thiếu Idea làm bài. Nhân tiện thì đây là code theo í tưởng của mình, ai tìm được lỗi thì có thể giúp mình sửa với a. Mình cảm ơn.

#include <bits/stdc++.h>
using namespace std;
long long a,b,i,temp;
bool snt(long long x) {
	if (x<2) return false;
	for (i=2;i<=sqrt(x);i++) 
		if (x%i==0) return false;
	return true;
}
bool check(long long a, long long b) {
	for (i=2;i<=a;i++) {
		if (snt(i)) {
			if (a%i==0 && b%i!=0) return false;
			if (b%i==0 && a%i!=0) return false;
		}
	}
}
int main () {
	cin>>a>>b;
	if (b>a) {
		temp=a;
		a=b;
		b=temp;
	}
	if (check (a,b)) cout<<"Yes";
	else cout<<"No";
}
#2

Do hàm check không return true. Vả lại nếu b > a và a, b đều nguyên tố thì sẽ sai.

Bài này ý tưởng đầu tiên là phân tích thừa số nguyên tố của a và b, rồi tìm ước nguyên tố khác nhau giữa hai phân tích.

Tính UCLN d của a và b có thể loại được 30% số cặp (A064018), còn 70% thì phân tích \frac{a}{d}, \frac{b}{d} và d sẽ đỡ hơn.

2 Likes
#3

hàm check của b luôn trả ra sai, nhưng đề bài có chỗ hơi khó hiểu, mình đang hiểu là nếu có chung 2 ước snt trở lên là đúng (vì theo như ví dụ thì vẫn còn vài snt nữa). Vậy thì hàm check b có thể để 1 biến đếm, mỗi lần tìm đc 1 ước snt thì cộng biến đếm lên, sau đó nếu biến đếm lớn hơn 2 thì return true. Ngoài ra thì vòng for của b nên so sánh 2 số đã cho xem số nào nhỏ hơn thì dùng chứ input ko mặc định số đầu là số nhỏ hơn.

#4

Trong ví dụ 2, 78 chia hết cho 13 nhưng 24 thì không.

UCLN chỉ chứa thừa số chung (có số mũ nhỏ hơn) của các số.
Vậy bài này chỉ cần làm 1 dãy UCLN, bắt đầu từ d = UCLN(a, b), sau đó lấy d1 = UCLN(a/d, d), d2 = UCLN(a/(d*d1), d)… đến khi d_n bằng 1 hay d_n chia hết cho a/d_n.

  • Nếu UCLN bằng 1 thì a/d_n có chia hết cho một thừa số riêng.
  • Nếu d chia hết cho a/d_n thì d_n không còn thừa số nào khác nữa, ngoài các thừa số chung.

VD:
a = 36 b = 24 => d = 12
36/12 = 3, 12 chia hết cho 3
24/12 = 2, 12 chia hết cho 2
=> true

a = 75 b = 15 => d = 15
75/15 = 5, 15 chia hết cho 5
15/15 = 1, 15 chia hết cho 1
=> true

a = 84 b = 28 => d = 28
84/28 = 3, UCLN(28, 3) = 1
=> false 84 = 3\cdot28 = 3\cdot(2^2 \cdot 7)

a = 78 b = 24 => d = 6
78/6 = 13, UCLN(13, 6) = 1
=> false 78 = 13\cdot6 = 13\cdot (2\cdot3)

Bài toán đưa về kiểm tra thừa số riêng của một số n so với UCLN d. Ta đặt ra hai dãy u, d:

  • u[1] := n/d, u[i] = u[i-1]/d[i-1] với
  • d[i] = UCLN(u[i], d)

Điều kiện dừng là tồn tại m để d[m] = u[m] hay d[m] = 1, vậy theo cách dựng thì n = u[m] * d * tích của d[1…m-1].

  • Nếu d[m] = u[m]: không còn thừa số nào để chia (xét đến) nữa => true
  • Nếu d[m] = 1: 1 chỉ chia hết cho chính nó nên chẳng có thừa số chung nào => false

Thuật toán sẽ dừng vì d[i] phải là ước của n.

2 Likes
Số nguyên tố tương đương
#5

Có thể duyệt các số nguyên tố từ nhỏ đến lớn và kiểm tra xem nó có là ước của hai số kia không

#6

Cách này tốn thời gian. Kiểm tra 1 số x có phải là ước của 2 số a và b chính là kiểm tra gcd(a, b) có chia hết cho x hay không mà.

1 Like
#7

Thực ra cách này chủ topic cũng đang làm.

#8

Hình như hàm check chỉ thiếu đúng một dòng: return true;

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