学步园

题意：

给定一个整数n，求∑fun(i,j)（1<=i<=j<=n）。其中fun(i,j)=∑i*j/gcd(i/k,j/k)(k为i和j的公因子)。

题解：

令答案ans=dp[n]，那么dp[n]=dp[n-1]+∑fun(i,n)(1<=i<=n)，dp[1]=1。所以我们只要求出所有的∑fun(i,n)(1<=i<=n)，就能求得多有的dp[i]。也就能在O(1)时间内输出结果了。

∑fun(i,n)(1<=i<=n)怎么求？我们先讨论fun(i,n)=n*(i/c1+i/c2+...)，其中cj为n和i的最大公约数d的所有因子。

那么我们可以枚举所有n的因子j，对于因子j，存在这个因子且小于等于n的数字中有j,2*j,3*j,...,n。我们可以得到s[j]=(1+2+3+...n/j)*n=(n/j+1)*(n/j)/2*n。那么val[n]=∑fun(i,n)(1<=i<=n)=∑s[j](j为n的因子)。

之后用dp[n]=dp[n-1]+val[n]递推公式就能求得结果了。

我一开始是将结果打出来找规律得到这个结论的。。

代码：

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

#define LL __int64
const int maxn=5e5+20;
LL mod;
LL val[maxn],dp[maxn];

void fun(int n)
{
    for(LL i=1;i<n;i++)//枚举因子
    {
        for(LL j=i;j<n;j+=i)//枚举含有因子的数
        {
            val[j]+=(j/i+1)*(j/i)/2;
        }
    }
}
void init()
{
    mod=1;
    mod=(mod<<32);
    memset(val,0,sizeof(val));
    fun(maxn);
    dp[1]=1;
    for(LL i=2;i<maxn;i++)//递推公式
    {
        dp[i]=dp[i-1]+val[i]*i;
        dp[i]=dp[i]%mod;
    }
}
int main()
{
    init();
    int n,tt=0,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("Case #%d: %I64d\n",++tt,dp[n]);
    }
    return 0;
}