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

#1

**Mấy a cho e hỏi hướng để tỉm tổng các ước của 1 số LỚN nguyên dương 1 cách nhanh nhất được không ạ ? **

Pasted image407×551 9.21 KB

e dùng code thế này vẫn đúng nhưng đếm rất chậm , và e nghĩ mãi không có hướng nào để làm nữa :frowning:

#include<iostream>
using namespace std;
int main()
{
    int n,s=0;;cin>>n;
    for(int i=1;i<n;i++)
    {
        if(n%i==0) s+=i;
    }
    cout<<s;
    return 0;
}
Tính tổng các ước thực sự của một số nguyên dương n
#2

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;	
}
6 Likes
#3

tks anh nhé vietha1996 :slight_smile:

#4

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à…@@

#5

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.

#6

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ó

#8

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 ạ?

#9

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

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).

4 Likes
#10 
// 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

#11

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

2 Likes
#12

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

#13

Ở đây lại có một dạng đối khác :slight_smile: [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à đủ.

2 Likes
#14

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

#15

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

2 Likes
#16

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

#17 
// 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

#18

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 :smiley:

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.

2 Likes
#19 
#include<bits/stdc++.h>

using namespace std;
 
int main() {
     int n,s=0;;cin>>n;
    for(int i=2;i<n;i++)
    
        if(n%i==0) s+=i;
    
    cout<<s;
    return 0;
	
}
#20

#include <bits/stdc++.h>
using namespace std;
long long n,tong=0;
int main()
{cin>>n;
for(int i=1;i<=sqrt(n);i++)
if(n%i==0)
tong=tong+n/i;
cout << tong;
return 0;
}
Mọi người xem code em còn thiếu sót ở đâu ạ

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