30/09/2018, 16:09
Tính tổng các ước của n số nhập vào từ bàn phím
Đề bài như thế này
Tính tổng các ước của n số nhập vào từ bàn phím
Input
Dòng đầu chứa số bộ test.
Các dòng sau, mỗi dòng chứa 1 số nguyên dương n
Output
Mỗi test in trên 1 dòng chứa 1 số nguyên là tổng các ước của test tương ứng đó.
n: số bộ test mình cần kiểm tra ví dụ:
Input:
2
5
6
Ouput:
6
12
Đây là Code của em. Cách này tuy đúng nhưng time chạy có vẻ lâu, mọi người còn cách nào chạy nhanh hơn không ạ?? Tối ưu nó càng chạy nhanh càng tốt. Em cảm ơn ạ!!
#include<iostream>
#include<math.h>
using namespace std;
void tong(int &a){
int s =0;
for(int i = 1 ;i <= a; i++){
if(a % i == 0){
s += i;
}
}
cout << s << endl;
}
int main(){
int n;
cout << "nhap so n = ";
cin >> n;
int b[100];
cout << "nhap cac so can tinh : ";
for(int i=0;i<n;i++){
cin >> b[i];
}
cout << "ket qua la : " << endl;
for(int i=0;i<n;i++){
tong(b[i]);
}
}
Bài liên quan
Anh chưa hiểu cái này là sao @Kudoshinichi, em giải thích kỹ hơn được không?
Em đừng đặt tên là
bnha, không có ý nghĩa gì. Em có thể khai báoCho anh hỏi thêm, ước là sao ta? Tức là các số chia hết hay sao. Ví dụ 10 có các ước
1 2 5 hả?
n: số bộ test mình cần kiểm tra ví dụ:
Input:
2
5
6
Ouput:
6
12
Vậy trong bài của em chưa có đọc file?
vâng, em sẽ chú ý chỗ mảng
thì em chỉ chạy vài test thôi anh nên em dùng mảng để nhập từ bàn phím ạ
10 thì là 1,2,5,10 mà anh
:v
em chỉ cần tối ưu sao cho nó chạy nhanh hơn thôi vì em nghĩ cách này cổ xưa quá. Nhưng chưa nghĩ ra .hi
@Kudoshinichi ơi, diễn đàn mình không phải là Facebook, mình không nên viết 1 câu, rồi post một bài như vậy. Như vậy em sẽ thấy là nội dung câu hỏi sẽ bị rời rạc không. Hãy tập trung viết trong một post thôi.
Anh thấy bài em khá ổn đấy, như vậy là được rồi
vâng, em sẽ lưu ý, nhưng có cách nào chạy nhanh hơn ko anh, em muốn giảm cái vòng lặp for kia đi nữa cơ anh ạ
Ý em là vòng lặp for này? Anh nghĩ như vậy là ổn
vâng ý em là chỗ đó đấy ạ, giả sử mình cần tính tổng các ước của số 1000 thì nó phải lặp tận 1000 à anh, phải làm sao cho nó chạy nhanh đc đây anh
Em sửa điều kiện lại thành
Bời vì nếu giả sử tìm ước của n thì ta có
n / a = b;=>
a*b = na lớn nhất khi
a == b=>
a <= sqrt(n)(sqrt = căn bậc 2)ok, tks anh ạ
@Gio Bạn muốn đặt câu hỏi hay sao?
Làm sao chèn Latex để điền công thức toán vậy? Hình như cái này chưa hỗ trợ
Cái này chưa hỗ trợ @Gio ơi.
Giờ em ví dụ số 12. Nếu chạy đến sqrt(12) thì sẽ chỉ chạy đến 3,3. Thiếu mất ước bằng 6 anh ạ
Bạn đưa về bài toán phân tích số n thành tích các số nguyên tố. Giả sử số n phân tích thành tích của m số nguyên tố. Thì output sẽ bằng 2 mũ m.
A xl. Mình nhầm một xíu
Một lần bạn lấy được cả hai số nhé, không sót đâu. 2*6 = 12 thì bạn lấy được cả số 6 rồi còn gì.
Áp dụng quy nạp trên số thừa số nguyên tố cũng đc.
Để tránh phải dùng tính chất UFD của N* ta c/m từ một u | mn sẽ phân tích được u = dd’ (d | m && d’ | n) duy nhất.
Đầu tiên ta c/m gcd(d, d’) = 1 với mọi (d, d’) thỏa mãn. Giả sử điều ngược lại, vậy gcd(d, d’) chia hết cả m và n, dẫn đến mâu thuẫn. Sau đó đặt d1, d’1 tương ứng sao cho dd’ = d1d’1 (hay d/d’1 = d1/d’), nhưng hai phân số này đều tối giản, suy ra đpcm.
Vậy sigma(d|m) d * sigma(d’|n) d’ = sigma(dd’ | mn) dd’ (do (d, d’) -> dd’ là một-một), hay sigma(m)sigma(n) = sigma(mn).