đếm số ước

[thuthuy7794]

các bạn chỉ mình bài này với!
cho số nguyen dương n.
hãy đếm xem n! co bao nhiêu ước số khác 1.

[lamtuenhi]

các bạn chỉ mình bài này với!
cho số nguyen dương n.
hãy đếm xem n! co bao nhiêu ước số khác 1.

Đáp:
- 0<=N<=1: 1
- N>1: có n-1 ước.
Chứng minh:
Từ định nghĩa N! = 1.2.3.4.5...N=> N chia hết cho các số lần lượt từ 1 đến N.
[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[thaymatkinhiphone6s]

Program DIEM_UOC;
Var i,GT,US,n,j:LongInt;

BEGIN
        Writeln('Nhap vao so n: ');
        Readln(n);
        GT:=1;
        US:=0;
        for i:=1 to n do
                GT:=GT*i;
        for j:=2 to GT do
              if (GT mod j)=0 then
                 US:=US+1;
        Writeln('So uoc: ',US);
        Readln;
END.

- Hihi các bạn sem có đúng ko nhá ^^ !

[duancanhotp]

Đáp:
- 0<=N<=1: 1
- N>1: có n-1 ước.
Chứng minh:
Từ định nghĩa N! = 1.2.3.4.5...N=> N chia hết cho các số lần lượt từ 1 đến N.
[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

N! còn chia hết cho chính nó nữa phải không ?

[datxanhmb81]

N! còn chia hết cho chính nó nữa phải không ?

Vì vậy nên có n-1 ước với n>1.
Code của bạn nếu N lớn quá thì cho kết quả sai [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[Minhpham.vcu]

VD: N=5
N!=1*2*3*4*5
U={2,3,4,6,8,10,12,15,20,....}

N! ko chỉ chia hết cho các số từ 1..N mà còn chia hết cho tích 2,3,4... số bất kì trong đó [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[nongdanseo]

Đáp:
- 0<=N<=1: 1
- N>1: có n-1 ước.
Chứng minh:
Từ định nghĩa N! = 1.2.3.4.5...N=> N chia hết cho các số lần lượt từ 1 đến N.
[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

4!=24 có ước 2,3,4,6,12,24 tức là có 6 ước <> 4-1=3 ước theo cách binhnguyen nói.
Bình nguyên sai lầm ở chỗ ước của N! có thể là 1 tích của các ước con (vd 12=3*4).

[tapchidoisong]

Cái của em làm không tối ưu !! N! vượt quá giới hạn LongInt ông anh có thuật nào khác hay hơn không ??

[clickenter]

Cái của em làm không tối ưu !! N! vượt quá giới hạn LongInt ông anh có thuật nào khác hay hơn không ??

Thuật toán của em là vét cạn :| và khi n lên tới 1x thì thời gian sẽ không được trong 1s. Vì thế cố gắng suy nghĩ thuật toán nào đó, dựa trên tư tưởng nhận xét nào đó để tính được đừng đi theo hướng vét cạn nữa. Và anh cũng đang đau đầu đây :|

[tungcar2084]

Cám ơn Ginta nhắc, nhầm lẫn tai hại :|

N-1
_
\
/_ C(N-1,i) mới là kết quả của bài toán.
i=1
Như vậy phải xây dựng chương trình tính tổ hợp C(n,k) :|
Bạn chủ topic, giới hạn của N là bao nhiêu...?