题目大意：给定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;
}版权声明：本文博客原创文章，博客，未经同意，不得转载。