hdu 4944 FSF’s game(数论)

题目链接：hdu 4944 FSF’s game

题目大意：给定N，可以用不大于N的长a和宽b，组成N∗(N−1)2种不同的矩形，对于每个矩形a∗b要计算它的值，K为矩形a，b可以拆分成若干个K∗K的正方形。∑a∗bgcd(a/k,b/k),输出所有矩形值的和。

解题思路：假设有边a和b，那么k肯定即使a的因子也是b的因子。定义f(n)为矩形最长边等于n的情况下所有矩形值的和。那么f(n)=val(1∗n)+val(2∗n)+⋯+val(n∗n),枚举n的因子作为k，现在假设有因子k，使得n=k∗a:
g(k)=1∗k∗nk+2∗k∗nk+⋯+a∗k∗nk

=1∗n+2∗n+⋯+a∗n

=(1+a)∗a2∗n

f(n)=∑g(k)（k为n的因子）
然后用类似素数筛选法的方式处理处f(i)的值，对应再累加即使答案。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef unsigned long long ll;
const ll MOD = 1LL<<32;
const int maxn = 500000;

ll f[maxn+5], s[maxn+5];

void init () {
    memset(f, 0, sizeof(f));

    s[0] = f[1] = 0;
    for (int i = 1; i <= maxn; i++) {

        for (int k = 1; k * i <= maxn; k++) {
            f[k*i] += (1LL + k) * k / 2;
            f[k*i] %= MOD;
        }
        f[i] = f[i] * i % MOD;
    }

    for (ll i = 1; i <= maxn; i++)
        s[i] = (s[i-1] + f[i]) % MOD;
}

int main () {
    init();
    int cas, n;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        scanf("%d", &n);
        printf("Case #%d: %I64u\n", kcas, s[n]);
        //printf("Case #%d: %lld\n", kcas, s[n]);
    }
    return 0;
}