HDU4944-FSF’s game（遞推）

HDU4944-FSF’s game（遞推）

題目鏈接

題意：給定一個整數n，求∑f(i, j)(1 <= j <= i <= n)。其中f(i, j) = i * j / gcd(i/k, j/k)(k為i, j的公因子)

思路：依題意，我們可以得到一個遞推式ans[n] = ans[n - 1] + ∑f(n, j)(1 <= j <= n), 如果我們可以預處理∑f(n,j)這一部分的話，就可以在O(n)情況下輸出答案。
對於∑f(n, j)而言，我們用aj(1 <= j <= n)表示gcd(n/k, j/k)所能取到的值的集合，那麼可以得到∑f(n, j) = (n * 1 / a1 + n * 2 / a2 + ... + n * n / an) = n * (1 / a1 + 2 / a2 + ... + n / an)，注意aj中的值一定是n的因子。所以我們就可以枚舉n的因子m，1m, 2m ... n，可以得到哪些aj中包含因子m，所以sum(m) = (1m / m) + (2m / m) + ... + (n / m) = (1 + n / m) * (n / m) / 2 。
所以∑f(n, j) = ∑sum(m)(m為n的因子)。

#include 
#include 
#include 
#include 

using namespace std;

typedef unsigned __int64 ull;
const int MAXN = 500000;
const ull MOD = (ull)1 << 32;

ull  ans[MAXN + 5], sum[MAXN + 5];
int n;

void init() {
    memset(ans, 0, sizeof(ans));
    memset(sum , 0, sizeof(sum));
    for (ull i = 1; i <= MAXN; i++)
        for (ull j = i; j <= MAXN; j += i)
            sum[j] += (j / i + 1) * (j / i) / 2;
    for (ull i = 1; i <= MAXN; i++) {
        ans[i] = ans[i - 1] + sum[i] * i;  
        ans[i] %= MOD; 
    }
}

int main() {
    int t = 1, cas;
    init();
    scanf("%d", &cas); 
    while (cas--) {
        scanf("%d", &n);
        printf("Case #%d: %I64u\n", t++, ans[n]);  
    }  
    return 0;
}