Saya harus mengimplementasikan penjumlahan ini dalam C ++. Saya sudah mencoba dengan kode ini, tetapi dengan angka yang sangat tinggi hingga 10^12 butuh waktu terlalu lama.

Penjumlahannya adalah: penjumlahan

Untuk sembarang bilangan bulat positif k, misalkan d(k) menyatakan banyaknya pembagi positif dari k (termasuk 1 dan k itu sendiri). Misalnya, untuk bilangan 4:1 memiliki 1 pembagi, 2 memiliki dua pembagi, 3 memiliki dua pembagi, dan 4 memiliki tiga pembagi. Jadi hasilnya adalah 8.

Ini kode saya:

#include <iostream>
#include <algorithm>

using namespace std;

int findDivisors(long long n) 
{
    int c=0;
    for(int j=1;j*j<=n;j++)
    {
        if(n%j==0)
        {
            c++;
            if(j!=(n/j))
            {
                c++;
            }
        }
    }
    return c;
}

long long compute(long long n)
{
    long long sum=0;
    for(int i=1; i<=n; i++)
    {
        sum += (findDivisors(i));
    }
    return sum;
}

int main()
{
    int n, divisors;

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    cin >> n;

    cout << compute(n);
}

Saya pikir ini bukan hanya masalah optimasi sederhana, tapi mungkin saya harus mengubah algoritma sepenuhnya. Adakah yang punya ide untuk mempercepatnya? Terima kasih.

1
user14584436 11 Mei 2021, 22:12

3 jawaban

Jawaban Terbaik

largest_prime_is_463035818 jawaban menunjukkan solusi O(N), tetapi OP mencoba menyelesaikan masalah ini

dengan angka yang sangat tinggi hingga 1012.

1/2

n/1 + n/2 + n/3 + ... + n/n

Secara khusus, kita dapat menghitung jumlah suku dengan nilai tertentu.

Pertimbangkan semua suku n/k di mana k > n/2. Jumlahnya n/2 dan semuanya sama dengan 1 (pembagian bilangan bulat), sehingga jumlahnya n/2.

Pertimbangan serupa berlaku untuk dividen lainnya, sehingga kita dapat menulis fungsi berikut:

long long count_divisors(long long n)
{
    auto sum{ n };
    for (auto i{ 1ll }, k_old{ n }, k{ n }; i < k ; ++i, k_old = k)
    { //                                    ^^^^^ it goes up to sqrt(n)
        k = n / (i + 1);
        sum += (k_old - k) * i;
        if (i == k)
            break;
        sum += k;
    }
    
    return sum;   
}

Di sini diuji terhadap algoritme O(N), satu-satunya perbedaan dalam hasil adalah kasus sudut n = 0 dan n = 1.

Sunting

Sekali lagi terima kasih kepada terbesar_prime_is_463035818, yang menautkan halaman Wikipedia tentang fungsi penjumlahan pembagi, di mana keduanya adalah O (N) dan algoritma O(sqrt(N)) disebutkan.

Implementasi yang terakhir mungkin terlihat seperti ini

auto divisor_summatory(long long n)
{
    auto sum{ 0ll };
    auto k{ 1ll };
    for ( ; k <= n / k; ++k )
    {
        sum += n / k;
    }
    --k;
    return 2 * sum - k * k;
}

Mereka juga menambahkan pernyataan ini:

Menemukan bentuk tertutup untuk ekspresi penjumlahan ini tampaknya berada di luar teknik yang tersedia, tetapi dimungkinkan untuk memberikan perkiraan. Perilaku utama dari seri ini diberikan oleh

D(x) = xlogx + x(2γ - 1) + (x)

di mana adalah konstanta Euler–Mascheroni, dan suku kesalahannya adalah (x) = O(kuadrat(x)).

1
Bob__ 12 Mei 2021, 20:53

Mari kita mulai dengan matematika dan kurangi faktorisasi O(n * sq(n)) menjadi O(n * log(log(n))) dan untuk menghitung jumlah pembagi, kompleksitas keseluruhannya adalah O(n * log(log(n)) + n * n^(1/3)).

Misalnya:

Dalam Codeforces himanshujaju menjelaskan bagaimana kita dapat mengoptimalkan solusi untuk menemukan pembagi suatu bilangan. Saya menyederhanakannya sedikit.

Let, n as the product of three numbers p, q, and r.

so assume p * q * r = n, where p <= q <= r. 
The maximum value of p = n^(1/3).

Now we can loop over all prime numbers in a range [2, n^(1/3)]
and try to reduce the time complexity of prime factorization.

We will split our number n into two numbers x and y => x * y = n. 

And x contains prime factors up to n^(1/3) and y deals with higher prime factors greater than n^(1/3).

Thus gcd(x, y) = 1.
Now define F(n) as the number of prime factors of n. 

From multiplicative rules, we can say that 

F(x * y) = F(x) * F(y), if gcd(x, y) = 1.

For finding F(n) => F(x * y) = F(x) * F(y)

So first find F(x) then F(y) will F(n/x)

And there will 3 cases to cover for y:
1. y is a prime number: F(y) = 2.
2. y is the square of a prime number: F(y) = 3.
3. y is a product of two distinct prime numbers: F(y) = 4.

So once we are done with finding F(x) and F(y), we are also done with finding F(x * y) or F(n).

Di Cp-Algorithm ada juga penjelasan yang bagus tentang cara menghitung jumlah pembagi pada nomor. Dan juga di GeeksForGeeks contoh pengkodean yang bagus tentang cara menghitung jumlah pembagi bilangan dengan cara yang efisien. Seseorang dapat memeriksa artikel dan dapat menghasilkan solusi yang bagus untuk masalah ini.

Penerapan C++

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 11;
bool prime[maxn];
bool primesquare[maxn];
int table[maxn]; // for storing primes

void SieveOfEratosthenes()
{

    for(int i = 2; i < maxn; i++){
        prime[i] = true;
    }

    for(int i = 0; i < maxn; i++){
        primesquare[i] = false;
    }

    // 1 is not a prime number
    prime[1] = false;

    for(int p = 2; p * p < maxn; p++){
        // If prime[p] is not changed, then
        // it is a prime
        if(prime[p] == true){
            // Update all multiples of p
            for(int i = p * 2; i < maxn; i += p){
                prime[i] = false;
            }
        }
    }

    int j = 0;
    for(int p = 2; p < maxn; p++) {
        if (prime[p]) {
            // Storing primes in an array
            table[j] = p;

            // Update value in primesquare[p * p],
            // if p is prime.
            if(p < maxn / p) primesquare[p * p] = true;
            j++;
        }
    }
}

// Function to count divisors
int countDivisors(int n)
{
    // If number is 1, then it will have only 1
    // as a factor. So, total factors will be 1.
    if (n == 1)
        return 1;

    // ans will contain total number of distinct
    // divisors
    int ans = 1;

    // Loop for counting factors of n
    for(int i = 0;; i++){
        // table[i] is not less than cube root n
        if(table[i] * table[i] * table[i] > n)
            break;

        // Calculating power of table[i] in n.
        int cnt = 1; // cnt is power of prime table[i] in n.
        while (n % table[i] == 0){ // if table[i] is a factor of n
            n = n / table[i];
            cnt = cnt + 1; // incrementing power
        }

        // Calculating the number of divisors
        // If n = a^p * b^q then total divisors of n
        // are (p+1)*(q+1)
        ans = ans * cnt;
    }

    // if table[i] is greater than cube root of n

    // First case
    if (prime[n])
        ans = ans * 2;

    // Second case
    else if (primesquare[n])
        ans = ans * 3;

    // Third case
    else if (n != 1)
        ans = ans * 4;

    return ans; // Total divisors
}

int main()
{
    SieveOfEratosthenes();
    int sum = 0;
    int n = 5;
    for(int i = 1; i <= n; i++){
        sum += countDivisors(i);
    }
    cout << sum << endl;
    return 0;
}

Keluaran

n = 4 => 8
n = 5 => 10

Kompleksitas

Kompleksitas waktu: O(n * log(log(n)) + n * n^(1/3))

Kompleksitas ruang: O(n)

Terima kasih, @largest_prime_is_463035818 untuk menunjukkan kesalahan saya.

-1
Badhan Sen 11 Mei 2021, 23:49

Saya menggunakan pendekatan brute force Anda sebagai referensi untuk memiliki kasus uji. Yang saya gunakan adalah

compute(12) == 35
cpmpute(100) == 482

Jangan bingung dengan faktorisasi komputasi. Ada beberapa trik yang bisa dimainkan saat memfaktorkan angka, tetapi Anda sebenarnya tidak memerlukan semua itu. Solusinya adalah loop O(N) sederhana:

#include <iostream>
#include <limits>

long long compute(long long n){
    long long sum = n+1;
    for (long long i=2; i < n ; ++i){
        sum += n/i;
    }
    return sum;
}

int main()
{
    std::cout << compute(12) << "\n";
    std::cout << compute(100) << "\n";
}

Keluaran:

35
482

Mengapa ini berhasil?

Kuncinya ada di komentar Marc Glisse:

Seperti yang sering terjadi pada masalah seperti ini, jumlah ini sebenarnya menghitung pasangan x, y di mana x membagi y, dan jumlah tersebut diatur untuk menghitung terlebih dahulu semua x yang sesuai dengan y tetap, tetapi tidak ada yang mengatakan Anda harus tetap seperti itu.

Saya bisa berhenti di sini, karena komentar sudah menjelaskan semuanya. Padahal, jika belum diklik...

Triknya adalah menyadari bahwa jauh lebih mudah menghitung pembagi semua bilangan hingga n daripada n-kali menghitung pembagi bilangan individual dan mengambil jumlahnya.

Anda tidak perlu mempedulikan faktorisasi dari misal 123123123 atau 52323423 untuk menghitung semua pembagi hingga 10000000000. Yang Anda butuhkan hanyalah perubahan perspektif. Alih-alih mencoba memfaktorkan angka, pertimbangkan pembagi. Seberapa sering pembagi 1 muncul hingga n? Sederhana: n-kali. Seberapa sering pembagi 2 muncul? Masih sederhana: n/2 kali, karena setiap bilangan kedua habis dibagi 2. Pembagi 3? Setiap bilangan ke-3 habis dibagi 3. Saya harap Anda sudah bisa melihat polanya.

Anda bahkan dapat mengurangi loop menjadi hanya loop hingga n/2, karena angka yang lebih besar jelas hanya muncul sekali sebagai pembagi. Meskipun saya tidak repot-repot melangkah lebih jauh, karena perubahan terbesar adalah dari O(N * sqrt(N)) Anda menjadi O(N).

1
largest_prime_is_463035818 11 Mei 2021, 22:21