题解

问题分析
本题要求计算一个 n×m表格中所有元素的和对 20101009 取模的结果，表格中第 i 行第 j 列的元素为 lcm(i,j)，即 i 和
j 的最小公倍数。

#include <iostream> 
#include <vector> 
using namespace std; 
 
const int MOD = 20101009; 
 
// 线性筛求莫比乌斯函数 
vector<int> mu, primes; 
vector<bool> isPrime; 
void sieve(int n) { 
    mu.resize(n  + 1); 
    isPrime.resize(n  + 1, true); 
    mu[1] = 1; 
    for (int i = 2; i <= n; ++i) { 
        if (isPrime[i]) { 
            primes.push_back(i);  
            mu[i] = -1; 
        } 
        for (int j = 0; j < primes.size()  && i * primes[j] <= n; ++j) { 
            isPrime[i * primes[j]] = false; 
            if (i % primes[j] == 0) { 
                mu[i * primes[j]] = 0; 
                break; 
            } 
            mu[i * primes[j]] = -mu[i]; 
        } 
    } 
} 
 
// 计算前缀和 
long long sum(long long x) { 
    return x * (x + 1) / 2 % MOD; 
} 
 
// 计算内层和 
long long innerSum(long long a, long long b) { 
    long long res = 0; 
    for (int k = 1; k <= min(a, b); ++k) { 
        res = (res + 1LL * mu[k] * k % MOD * k % MOD * sum(a / k) % MOD * sum(b / k) % MOD) % MOD; 
    } 
    return res; 
} 
 
// 计算最终结果 
long long solve(int n, int m) { 
    long long res = 0; 
    for (int d = 1; d <= min(n, m); ++d) { 
        res = (res + 1LL * d * innerSum(n / d, m / d)) % MOD; 
    } 
    return (res + MOD) % MOD; 
} 
 
int main() { 
    int n, m; 
    cin >> n >> m; 
    sieve(min(n, m)); 
    cout << solve(n, m) << endl; 
    return 0; 
} 

欢迎入队