Tính số các ước và tổng các ước của N! (N <= 100)

Mọi người cho e hỏi bài này chút với:

Bài của e để đây: https://ideone.com/rHCd21

#include<bits/stdc++.h>
using namespace std;
int compare(string a, string b){
   while(a.size()<b.size()) a='0'+a;
   while(b.size()<a.size()) b='0'+b;
   if(a<b) return 1;
   else if(a==b) return 0;
   else return -1;
}
string sum(string a, string b){
    int x,y,tong,nho=0;
    string c="";
    while(a.size()<b.size()) a='0'+a;
    while(b.size()<a.size()) b='0'+b;
    for(int i=a.size()-1;i>=0;i--){
        x=a[i]-48;
        y=b[i]-48;
        tong=x+y+nho;
        nho=tong/10;
        c=char(tong%10+48)+c;
    }
    if(nho>0) c='1'+c;
    return c;
}
string chia(string a, int k){
   string t="";
   int du=0;
   int thuong;
   for(int i=0;i<a.size();i++){
      du=du*10+(a[i]-48);
      thuong=du/k;
      du=du%k;
      t=t+char(thuong + 48);
   }
   while(t[0]=='0'&&t.size()>1) t.erase(0,1);
   return t;
}
int mod(string a, int k){
   int du=0;
   for(int i=0;i<a.size();i++){
      du=du*10+(a[i]-48);
      du=du%k;
   }
   return du;
}


int main(){
		
	string a;
	int k;
	cin >> a;
    int d = 0;
    for(string i = "1"; (compare(i,a)==1||compare(i,a)==0);i = sum(i, "1")){

        while(mod(i,5)==0){
            i=chia(i,5);
        	d++;
        }
    }
    cout<<chia(a,5);
}

Chạy theo kiểu này nó cứ bị lỗi chỗ nào ý ạ, mọi người giúp e với!!!

2 Likes

Bạn không thể nhân chay tính N! rồi mới bổ ra các ước của nó, như vậy rất mất thời gian. Gợi ý là phân tích ra thừa số nguyên tố rồi áp dụng công thức.

4 Likes

số lượng ước thì có thể đếm được và dùng tổ hợp để tính, miễn cưỡng cũng có thể tính được (nhưng chắc cũng không dễ vì kết quả rất là lớn, sơ sơ 25 số nguyên tố với số mũ 1 2 3 4 5 6, cũng hơi mệt)
trong số các ước có 1 ước lớn nhất là 50*99! thì sao tính ra đây nhỉ, không lẽ lại phải dùng mảng biểu diễn số nguyên lớn nhỉ :smiley:
có vẻ không khó nhưng dễ bị rối

4 Likes

Đúng vậy, giai thừa tức là cho sẵn dạng tích rồi mà :smiley:

5 Likes

Ý bạn là từ công thức n! = n * (n-1) * … * 2 * 1
ta phân tích n, (n-1), (n-2) … ra thành các thừa số nguyên tố, rồi tính tổng và đếm các ước này đúng k?
Tôi thấy không ổn á, vì ta phải loại đi các ước trùng nhau và thiếu những ước là tích của vài thừa số nguyên tố á
VD: n! = 6! = 6 * 5 * 4 * 3 * 2 * 1
=> ước là: (2, 3, 6, 1), (5, 1) , ( 2, 2 , 4 , 1 ) , (3, 1) , (2, 1) * 1
Thực tế các ước của 6! = 720 = 6, 5, 4, 3, 2, 1, 36, 24, 20, 18, 16, 15, 12, 10, 9, 8
Hay tôi hiểu sai ý bạn?

1 Like

Chắc vậy :slight_smile: đây là Số học cơ bản.
Ví dụ với thừa số 3, từ 1 đến N cứ 3 số có 1 số chia hết cho 3 => N div 3 thừa số :slight_smile:
cứ 9 số có 1 số chia hết cho 3^2, mà nãy ta lấy được 1 thừa số 3 => N div 9 thừa số…

3 Likes

Tức là sao? Chưa hiểu gì luôn!
Bạn tính tổng những ước của N! như thế nào vậy?

Thì đó là cách phân tích thừa số thôi :smiley: từ phân tích tính tổng thì cái này mình có viết rồi.

3 Likes

ở đâu vậy bạn? tự dưng thấy ngu quá, k nghĩ được thuật toán luôn, đọc cmt mà càng loạn não

4 Likes

để tôi ngâm cứu thử. Thanks bạn

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