Thuật toán tính tổng các ước của 1 số nguyên dương?

Bạn cho i chạy tới căn bậc 2 của n thôi, nếu chia hết thì cộng thêm i và n / i vào.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int n;
	int s = 0;
	
	cin >> n;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0) {
			int j = n/i;
			if (i == j) {
				s = s + i;
			} else {
				s = s + i + j;
			}
		}
	}
	cout << "s = " << (s - n);
	
	return 0;	
}

tks anh nhé vietha1996

chỗ đk :

int j = n/i;
if (i == j) {
s = s + i;
}

làm sao xảy ra số i và j được nhỉ j=n/i mà…@@

Trường hợp này để kiểm tra những số chính phương.

Ví dụ n = 9, khi cho i chạy đến 3 thì j = n / i = 3
=> như vậy ước số 3 sẽ bị cộng 2 lần.

for(int i=1;i<n;i++)

chạy đến n/2 thôi bạn, không nhất thiết phải chạy đến n đâu vì ước của 1 số luôn <= 1/2 số đó trừ chính nó

Bài này có thể dùng phân tích thừa số nguyên tố

Người ta kí hiệu tổng ước là sigma(n) (sigma thường nhé).
Nếu n = p^k với p là số nguyên tố thì sigma(n) = 1 + p + p^2 + … + p^k = (p^(k+1) - 1)/(p-1).

Tổng quát hóa như sau: Cho q là một số nguyên tố sao cho gcd(q, n) = 1. Vậy ước của nq^k’ sẽ có dạng (ước của n)q^i với 0<=i<=k’. Vậy
sigma(nq^k’) = sigma(d|n) (dsigma(q^k’)). (sigma hoa :D) = sigma(q^k) * sigma(d|n) (d) = sigma(n) * sigma(q^k).

Từ đây suy ra sigma(n) = tích các sigma (thường) của thừa số nguyên tố.

Biến tổng có lẽ nên là 64 bit cho chắc ăn.

xin góp ý với các bạn,anh, chị ở đây là: ước số của 1 số nguyên dương thì luôn có 2 giá trị đối nhau, 1 âm và 1 dương, do đó tổng luôn bằng 0. nhưng giả sử đề ở đây ko phải là tổng các ước số mà là tích các ước số thì cho em hỏi là phải code như nào để lấy được tích của cả ước âm và dương ạ?

Đề thường chỉ nói đến ước dương thôi, ít ai nói đến ước âm.

phải code như nào để lấy được tích của cả ước âm và dương

Lấy danh sách các ước dương, các ước âm chỉ là đối của các ước dương.

Đếm xem n có bao nhiêu ước, nếu số ước lẻ thì tích các ước (cả âm và dương) sẽ âm, ngược lại tích các ước sẽ dương.

Lấy bình phương tích các ước dương, rồi nhân với dấu (đã biết dựa vào số ước của n).

// tinh tich cac uoc so cua so nguyen duong n
#include<stdio.h>
#include<conio.h>
int i, n;
int tich=1;
int main()
{
	printf("Nhap vao gia tri n: ");
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{ if(n%i==0)
	tich*=i*(-i);}
	printf("tich la: %i", tich);
	return 0;
	}

em code thế này được ko nhỉ? thử lại với vài số thì cũng ra kqua đúng

Nếu n=10000 thì sao? Tích có thể nằm gọn trong khoảng int được không?

vậy phải sửa int thành gì ạ?

ước số của 1 số nguyên dương thì luôn có 2 giá trị đối nhau, 1 âm và 1 dương

Ở đây lại có một dạng đối khác [spoiler]p và n/p[/spoiler]
Vậy thì phân tích thừa số để đếm ước và [spoiler]kt bình phương[/spoiler] là đủ.

là sao ạ?
đây là anh đang nói về bài toán tính tổng hay tích các ước ạ?
nếu là tính tổng thì mặc định là tổng bằng 0 nếu tính cả ước âm rồi, còn phân tích thừa số làm gì cho mệt ạ?
ví dụ ước của 2 là: -2,-1,1,2 thì tổng bao giờ chả bằng 0

còn phân tích thừa số làm gì cho mệt ạ

Đang nói về tính tích mà. Vì vậy mới “có một dạng đối khác”.

em nghĩ như vậy là tự làm khó nó lên thôi mà, cụ thể nhé, ví dụ n=10; cho 1 ước bằng 2 thì ý anh có phải dạng đối khác ở đây là 10/2=5 đúng ko ạ? vậy cũng có giải quyết đc gì, ta cứ viết code tìm ước dương của nó, sau đó tính tích các ước thì nhân với giá trị âm tương ứng thôi

//dem so luong uoc so cua so nguyen duong n
#include<stdio.h>
#include<conio.h>
int n,i,so_uoc=0;
int main()
{
	printf("Nhap vao so nguyen duong n: ");
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{if(n%i==0)
	so_uoc++;}
	printf("so_uoc la: %d", so_uoc);
	return 0;
	}

trên kia có 1 anh bảo sửa i vì n bằng 10000 thì quá tải, em nghĩ code như này là cũng ổn rồi

// tinh tich cac uoc so cua so nguyen duong n
#include<stdio.h>
#include<conio.h>
int i, n;
int tich=1;
int main()
{
	printf("Nhap vao gia tri n: ");
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{ if(n%i==0)
	tich*=i*(-i);}
	printf("tich la: %i", tich);
	return 0;
	}

đây, em cop nhầm

vậy cũng có giải quyết đc gì

Vậy là bạn chưa rõ rồi. Khi chia cho p thì đồng thời thu được n/p và ngược lại, nên không hề vô ích. Để không bị trùng, ta chọn p là số bé hơn, vậy thì chỉ cần chia tới … ? là được

Ngoài ra, khi đã biết p với n/p kết thành cặp (p * n/p = n), thì khi tính tích ta chỉ cần quan tâm đến số ước. Bạn quay lên trên sẽ thấy ngay bài mình viết 1 năm trước về cái này.