Jumlahin Jumlahnya Jumlah Faktor

Soal#

Informasi#

• Sumber: CompFest 7 - Final CPC Junior

Arsip#

• TLX

Ringkasan#

Hitunglah nilai $S$ (modulo $10^9 + 7$) di mana $$S = \sum_{i = 1}^A \sum_{j = 1}^B f(GCD(i, j))$$

• $f(x) = \sum_{d | x} d$, yaitu jumlahan semua pembagi dari $x$, dan
• $GCD$ adalah fungsi untuk menghitung FPB (faktor persekutuan terbesar/greatest common divisor) dari dua bilangan.

Solusi#

Petunjuk#

Pembahasan#

Solusi naif dapat dengan mudah diimplementasi dengan membuat perulangan dua tingkat yang akan menghitung FPB dari $i$ ($1 \le i \le A$) dan $j$ ($1 \le j \le B$) lalu menjumlahkan semua pembaginya. Mari kita ubah cara menyelesaikan soal ini. Kita akan menghitung banyaknya kontribusi dari suatu bilangan terhadap jumlahan $S$ dari semua pasangan $i$ dan $j$.

Perhatikan bahwa untuk suatu $i$, bilangan-bilangan yang berkontribusi ke jumlahan akhir adalah semua pembagi dari $i$. Misalkan pembagi-pembagi dari $i$ adalah $d_1$, $d_2$, ..., dan $d_n$. Untuk suatu $d_k$, banyaknya $j$ di mana $d_k$ habis membagi $GCD(i, j)$ adalah $\left\lfloor\frac{B}{d_k}\right\rfloor$. Jadi kontribusi $d_k$ ke jumlahan akhir adalah $\left\lfloor\frac{B}{d_k}\right\rfloor \cdot d_k$. Oleh karena itu, $S$ dapat ditulis sebagai berikut. $$S = \sum_{i = 1}^A \sum_{d_k | i} \left( \left\lfloor\frac{B}{d_k}\right\rfloor \cdot d_k \right)$$

Kode#

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1E9 + 7;

int A, B;

int main(){
    cin >> A >> B;

    int ans = 0;
    for(int i = 1; i <= A; i++){
        vector <int> divs;
        for(int j = 1; j * j <= i; j++){
            if(i % j == 0){
                divs.push_back(j);
                if(j * j != i)
                    divs.push_back(i/j);
            }
        }

        for(const int& d : divs){
            ans += 1LL * B/d * d % MOD;
            ans %= MOD;
        }
    }

    cout << ans << '\n';
    return 0;
}