Tìm cặp số bạn bè (amicable pairs)

[buitrungbao (Bùi Trung Bảo)]

Đề bài: Người dùng nhập n. Hãy tìm các số p, q (0 < p < q < n) sao cho tổng các ước số thực sự của p bằng q và tổng các ước số thực sự của q bằng p. Tìm một thuật toán hiệu quả khi n lớn
Em dùng thuật toán 2 vòng lặp nên nó chạy rất lâu khi n lớn, có ai có ý tưởng thuật toán hiệu quả hơn không ạ?
Bài code của em: https://drive.google.com/open?id=13p_0CnK3XCLs-N-HvPooRbAsvYKLcOGj

#include <stdio.h>
int tongUocSo (int a){
	int sum = 0;
	for (int i = 1; i < a; i++)
		if (a % i == 0) sum += i;
	return sum;
}
void cau4(){
	int n, flag = 1;
	printf("Nhap n: ");
	scanf("%d", &n);
	for (int i = 1; i < n; i++){
		for (int j = i + 1; j < n; j++){
			if (tongUocSo(i) == j && tongUocSo(j) == i){
				if (i > j){
					printf("p = %d\nq = %d\n", j, i);
					flag = 0;
				} else {
					printf("p = %d\nq = %d\n", i, j);
					flag = 0;
				}
			}
		}
	}
	if (flag == 1) printf("Khong ton tai p va q trong khoang 0 toi %d\n", n);
}
int main(){
	cau4();
}

Mong cao nhân chỉ giáo. Em cảm ơn.

[rogp10]

Tính tổng ước thì cách nhanh nhất là thông qua phân tích thừa số nguyên tố do tổng ước có nhân tính (multiplicative) với các số nguyên tố cùng nhau.

Và chỉ cần chia tới sqrt(n) thôi.

[noname00 (HK boy)]

n lớn thì tra bảng thôi

Amicable numbers

[Nguyen_Hoang_Long1 (Nguyễn Hoàng Long)]

Hàm tìm ước số thực sự bạn cho chạy tới a/2 thôi.
I vs j cũng loại bớt thay vì cho chạy hết

[buitrungbao (Bùi Trung Bảo)]

i với j loại như thế nào vậy anh?

[buitrungbao (Bùi Trung Bảo)]

em hơi khó hiểu ạ phân tích thừa số nguyên tố là phép nhân mà làm sao thành tổng vậy anh

[noname00 (HK boy)]

a/2

Chỉ cần đến sqrt(a) thôi nhé.

i với j loại như thế nào vậy anh?

Bạn chỉ cần kiểm tra lại tongUocSo(tongUocSo(i)) có bằng i hay không thôi. Do vậy vứt đi được vòng lặp j vô nghĩa.

phân tích thừa số nguyên tố là phép nhân mà làm sao thành tổng vậy anh

Bạn đọc cmt này và tìm hiểu thêm trên google.

Cần giúp tăng tốc bài toán hơn ạ!

Một dạng quy nạp đấy c/m tổng ước của n bằng tích tổng ước các thừa số nguyên tố của n, hay S(p1^j1 * p2^j2 * …) = S(p1^j1) * S(p2^j2) * … với p1, p2… nguyên tố và đôi một khác nhau. Đầu tiên đương nhiên S(p1^j1) = S(p1^j1) rồi. Xét n’ = n * p_i^j_i với gcd(p_i, n) = 1 ta có d | n <=> p_i^k*d | p_i^k*n (với k = [0.. j_i]) => p_i^k*d | p_i^j_i*n. Tức là các ước của n’ có dạng p_i^k*d. Cộng lại: sigma(k=0..j_i) sigma(d | n) (p_i^k*d) = sigma(k=0..j_i) (p_i^k * sigma(d | n)(d)) = s…

[rogp10]

Để mình đọc lại đã rồi xong.

Cách 1: Cho m1, m2 là ước của m; n1, n2 là ước của n.
Nếu m1n1 = m2n2 thì m1/n2 = m2/n1
Vì nếu UCLN(m1, n2) != 1 thì mâu thuẫn, nên hai phân số đều tối giản. Vậy tử bằng tử, mẫu bằng mẫu, suy ra đpcm.

Cách 2: Với m, n nguyên tố cùng nhau thì
m’ | m => m’ | mn
n’ | n => n’ | mn
m’, n’ | mn <=> BCNN(m’, n’) | mn (định nghĩa)
Nếu UCLN(m’, n’) != 1 thì UCLN(m, n) != 1
do tích = UCLN * BCNN nên tìm được song ánh {ước của m} x {ước của n} -> {ước của mn} là (m’, n’) -> m’n’

[Gio (Gió)]

Dùng sàng nguyên tố để chứa thông tin 1 thừa số nguyên tố của mảng f O(nloglogn)
Các số có thể phân tích ra thừa số nguyên tố từ thông tin mảng f trong O(nlogn)
dùng bảng lưu kết quả và kiểm tra O(n)

ideone https://ideone.com/Clj1Lv

n = int(input())
f = [0]*(n+1)

for i in range(2,int(n**.5)+1):
	if f[i] == 0: # so nguyen to
		for j in range(i*i,n+1,i):
			f[j] = i

def sumdiv(x):
	x_ = x
	d = {}
	while f[x] != 0:
		d[f[x]] = d.get(f[x],0)+1
		x//=f[x]
	d[x] = d.get(x,0)+1
	ans = 1
	for k,v in d.items():
		ans*=(k**(v+1)-1)//(k-1)
	return ans-x_

T = [ 0 if i<2 else sumdiv(i) for i in range(n+1)]

for i in range(2,n+1):
	if T[i]!=i and i<=T[i]<=n and T[T[i]]==i:
		print(i,T[i])
		

[tntxtnt]

sao ko tạo mảng sumdiv[n] thẳng theo kiểu sàng luôn, cho i chạy từ 1 tới n bước 1, j từ 2*i tới n bước i, gán sumdiv[j] += i cũng O(nlogn) (n/2 + n/3 + n/4 + n/5 +… +n/(n-1) + n/n = n(1/2 + 1/3 + 1/4 + 1/5 + … + 1/(n-1) + 1/n) = O(nlogn)) tạo cái sàng nguyên tố làm gì

ko biết đúng ko

sửa lại i 1…n j 2*i…n step i :V

edit: n = 1e6 chạy mất 3.6s ko nhanh bằng 3s nhưng mà trong sáng hơn nhoa :V

n = int(input())

sumdiv = [1]*(n+1)
for i in range(2, n+1):
    for j in range(2*i, n+1, i):
        sumdiv[j] += i
        
for p in range(1, n):
    q = sumdiv[p]
    if p < q < n and sumdiv[q] == p:
        print(p, q)

[rogp10]

C (chạy sàng full)
n = 1e6 0.01s (page size)
n = 2e6 0.05s
n = 5e6 0.23s
n = 1e7 0.6s
n = 4e7 2.9s
n = 1e8 TLE

còn cơm gạo thì phải ntn. https://sech.me/ap/articles.html

[buitrungbao (Bùi Trung Bảo)]

Em làm theo cách của anh ra kết quả có vẻ đúng, anh xem giúp em còn chỗ nào thừa thải không ạ
Code:

#include <stdio.h>
#include <math.h>
int tongUocSo(int a) {
    int sum = 0;
    for (int i = 1; i < sqrt(a); i++)
        if (a % i == 0) {
            sum += i + a/i;
        }
    return sum - a;
}
void cau4() {
    int n, flag = 1;
    printf("Nhap n: ");
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        if (tongUocSo(tongUocSo(i)) < tongUocSo(i) && tongUocSo(tongUocSo(i)) == i) {
            printf("p = %d\nq = %d\n\n", tongUocSo(tongUocSo(i)), tongUocSo(i));
            flag = 0;
        }
    }
    if (flag == 1) printf("Khong ton tai p va q thoa man de bai\n");
}
int main() {
    cau4();
}

Những cách còn lại của mấy anh nâng cao quá, em mới sinh viên năm nhất thôi
Thảo luận rôm rả vầy em học được nhiều thứ mới
Cảm ơn mấy anh nhiều

[noname00 (HK boy)]

for các ước thực sự, bạn for từ 2 đến sqrt(a), tức là

for (int i = 2; i <= sqrt(a); i++)
    if (a % i == 0) {
        if (i * i == a)
            sum += i; // trường hợp này chỉ cần + 1 số, vì i == a / i
        else
            sum += i + a / i; // trường hợp này cần cộng 2 số, vì 2 số phân biệt
    }

return sum + 1; // không cần - a nữa, vì ta chỉ kể các ước thực sự trong khoảng [2, a / 2]
// nhưng ta cần + 1 vì 1 cũng là ước thực sự

Bạn mới for đến < sqrt(a), như vậy sẽ làm mất đi ước căn của a (nếu a là số chính phương).

Trong vòng for i trong void cau4(), bạn gọi tongUocSo(i) khá nhiều lần. Nên gán nó vào 1 biến nào đó để tránh tính đi tính lại nhiều lần.

[buitrungbao (Bùi Trung Bảo)]

Hiểu rồi, hay quá anh ạ Tối rồi em đi ngủ đây, chúc anh ngủ ngon :v

[rogp10]

Bài này mà tính tay bo thì dù có dùng sàng cũng 10^9 là bứt gân trong khi giới hạn hiện tại là 4*10^19 10^20.

https://sech.me/boinc/Amicable/forum_thread.php?id=91
https://sech.me/boinc/Amicable/forum_thread.php?id=183

Kĩ thuật loại trừ: https://sech.me/ap/articles.html#a1

[Tan_Truong1 (Tân Trương)]

sao phải kèm điều kiện tongUocSo(tongUocSo(i)) < tongUocSo(i) vậy ạ, e không hiểu đoạn này lắm

[rogp10]

Nếu không sẽ bị trùng, kiểu (a, b) với (b, a), hay (a, a) (số hoàn hảo).

[H1A4C3K]

code mình chạy ngon nha bạn
nhập 10 000 vào chạy ổn dưới 0.5s. 100 000 có hơi lâu khoảng 7-8s gì đó

#include <bits/stdc++.h>
using namespace std;
int main(){
    int b = 0, c = 0, d;
    cin >> d;
    cout << "\n\n\n\n\n";
    for(int a = 1; a <= d; ++a){
        b = 0; c = 0;
        for(int i = 1; i < a; ++i){
            if(a % i == 0){
                b += i;
            }
        }
        for(int i = 1; i < b; ++i){
            if(b % i == 0){
                c += i;
            }
        }
        if(a == c && a < b){
            cout << a << " and " << b << "\n";
        }
    }
    
}

[noname00 (HK boy)]

Code O(n^2) đâu có lợi gì đâu bạn. Chủ thớt muốn 1 thuật toán hiệu quả với số lớn để chạy trong khoảng 1-2s kìa.

[rogp10]

Code này đâu khác gì code ở đầu thớt đâu.