Tìm số phong phú trong đoạn [L; R] với L, R <= 10^6

#1

Chào anh chị. Em có một bài tập là tìm xem có bao nhiêu số phong phú trong đoạn [L;R]. Số phong phú là số có tổng các ước không kể nó lớn hơn nó. Ví dụ như số 20: 1+2+4+5+10=22>20 là số phong phú. Giới hạn: 0 < L, R<=10^6. Bài này thì em định khai báo trực tiếp các số vào mảng nhưng không được do có qua nhiều, nó giật máy em mà lag luôn. Vậy cho em hỏi còn cách làm nào khác không ạ? Em suy nghĩ cả 3 4 ngày nay mà nghĩ không ra, tại giới hạn của nó quá lớn. Em chạy thử từ 1 -> 10^6 có tới 247545, có quá nhiều. Em cám ơn ạ.

#2

Bạn có thể dùng sàng nguyên tố để phân tích một số ra thừa số nguyên tố. Từ đó dễ dàng tính tổng uớc.

2 Likes
#4

nhưng vd như số 12 thì nó còn là ước 4 với 6, 4 với 6 ko phải là số nguyên tố thì sao bạn?

#5

mình nói là dùng sàng nguyên tố để phân tích thành nhân tử( Sàng nguyên tố và một số ứng dụng)
Giả sử n=p1^e1 * p2 ^e2 … pn^en
thì tổng ước của nó là:

Code tham khảo:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define maxn 1000001

int f[maxn];

void sieve(){
    memset(f,sizeof(f),0);
    int i,j;
    for(i=2;i*i<maxn;i++){
        if(f[i]) continue;
        for(j=i*i;j<maxn;j+=i){
            if(f[j]) continue;
            f[j]=i;
        }
    }
}

int tong_uoc(int n){
    int res=1,pre=0,tmp;
    while(f[n]){
        if(f[n]!=pre){
            if(pre){
                res*=(tmp*pre-1)/(pre-1);
            }
            pre=f[n];
            tmp=pre;
        }else{
            tmp*=f[n];
        }
        n/=f[n];
    }
    
    if(n!=pre){
        if(pre) res*=(tmp*pre-1)/(pre-1);
        res*=n+1;
    }else{
        res*=(tmp*n*n-1)/(n-1);
    }
    return res;
}

int main() {
    sieve();
    int cnt=0,i;
    for(i=1;i<maxn;i++){
        if(tong_uoc(i)>2*i) cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}
3 Likes
#6

Cái đó có nghĩa gì vậy anh?

#7

Nếu f[i]!=0 thì tiếp tục vòng lặp, bỏ qua câu lệnh phía sau

2 Likes
#8

nói thật em chả hiểu code anh :((

#9

cái công thức trên thì pi là gì vậy anh? ei là gì anh?

#10

Pi ei lần luot là thừa số nguyên tố và số mũ

1 Like
#11

Em làm như anh vầy thì sao lại sai anh? Em cũng làm như công thức đó mà?
Em làm theo vd 12=2^2+3 => (2^0+2^1+2^2)*(3^0+3^1)=28 mà ước ko tính nó nên trừ đi nó là 16 là đúng mà sao kết quả ra sai anh :frowning:

    int main()
{
    int l, r, dem=0, ngto[4]= {2, 3, 5, 7};
    fi >> l >> r;
    for (int i=l; i<=r; i++)
    {
        int s=1, n=i, u;
        for (int j=0; j<4; j++)
        {
            int demso=0, tong=0;
            if (n%ngto[j]==0)
            {
                while (n%ngto[j]==0)
                {
                    demso++;
                    n/=ngto[j];
                }
                while (demso>=0)
                {
                    tong+=pow(ngto[j], demso);
                    demso--;
                }
                s*=tong;
            }
        }
        if (n>1)
        {
            int h;
            h=1+n;
            s=s*h-i;
        }
        if (n<=1) s=s-i;
        if (s>i) dem++;
    }
    fo << dem;
    fi.close();
    fo.close();
}
#12
  • số nguyên tố từ 0 đến 10^3 rất nhiều, không chỉ là 4 số trên. Nếu bạn phân tích thành nhân tử theo thuật toán của bạn thì phải tìm hết
  • công thức tính tổng ước đã gọn rồi bạn lại chia ra làm gì: s*=(pow(ngto[j], dem+1)-1)/(ngto[j]-1) bỏ qua dc cả đoạn while
1 Like
#13

cái công thức đó áp dụng sau mỗi lần chia cho ngto[j] hả anh?

#14

Thay cho đoạn while(dem>=0)…

#15

Bài này sàng 2…sqrt(n) sẽ O(n + sqrt(n)*logn), đỡ hơn O(n*sqrt(n)).

Cách sàng là chơi hẳn từ 2 đến sqrt(n) không bỏ số nào (khác với sàng số nguyên tố).

Ta có T = 1 + 1/2 + 1/3 +… + 1/sqrt(n) = theta(logn):

Áp dụng tích phân Darboux với y = 1/x là một hàm đơn điệu giảm trên [1…sqrt(n)]

S[1,n] (dx/x) < sigma[1..n](1/i) = T
< S[1,sqrt(n)] (dx/(x+1))
<=> ln(n)/2 < T < ln(n+1)/2
<=> 0 < T - ln(n)/2 < ln(1+1/n))/2

dùng định lí kẹp vậy T = theta(ln(n)).

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