InputThere are multiply test cases.
The first line contains an integer T(T<=500000), the number of test cases
Each of the next T lines contain an integer N(N<=500000).OutputOutput a single line for each test case.
For each test case, you should output "Case #C: ". first, where C indicates the case number and counts from 1.
Then output the answer, the value of that UNSIGNED 32-BIT INTEGER variable.Sample Input
3 1 3 100
Sample Output
Case #1: 1
Case #2: 30
Case #3: 15662489
HinIn the second test case, there are six levels(1x1,1x2,1x3,2x2,2x3,3x3)Here is the details for this game:
1x1: 1(K=1); 1x2: 2(K=1); 1x3: 3(K=1); 2x2: 2(K=1), 4(K=2); 2x3: 6(K=1); 3x3: 3(K=1), 9(K=3); 1+2+3+2+4+6+3+9=30
根据题意写出式子，ans[n]=ans[n-1]+∑ n*i*k/gcd（n,i）
∑ n*i*k/gcd（n,i） //gcd(n,i)/k 为n的因子,
=n?(1/a1+2/a2+?+n/an) //gcd(n,i)/k =ai，ai为n的因子
也就是说每个n的值对应了n的所有因子的贡献值之和。
比如n=2,因子1,2.
1的贡献 2 4
2的贡献 2
设mi为ai的因子 ∑ n*i*k/gcd（n,i）=n*[（1*m1/m1+2*m1/m1+...n/m1） +（1*m2/m2+2*m2/m2+...n/m2） +........+（1*mn/mn+2*mn/mn+...n/m）] //主要想清楚k/gcd（）的值,k的变化对应mi的值
设sum（mi）=（1*mi/mi+2*mi/mi+...n/mi）=（n/m）*（n/m+1）/2
ans[n]=ans[n-1]+sum(mi)*mi
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
typedef long long LL;
#include<algorithm>
using namespace std;
#define N 500005
const LL mod=1LL<<32;
LL ans[N];
LL num[N];
int main()
{
//freopen("i.txt","r",stdin);
//freopen("o.txt","w",stdout);
for(int i=1;i<N;i++)
{
for(LL j=i;j<N;j+=i)
{
num[j]+=(j/i)*(j/i+1)/2;
//cout<<j<<" "<<num[j]<<endl;
}
}
ans[1]=1;
for(LL i=2;i<=500000;i++)
{
ans[i]=ans[i-1]+num[i]*i%mod;
ans[i]%=mod;
//cout<<ans[i]<<endl;
}
int t;
scanf("%d",&t);
for(int l=1;l<=t;l++)
{
int n;
scanf("%d",&n);
cout<<"Case #"<<l<<": "<<ans[n]<<endl;
}
}
原文：http://www.cnblogs.com/ygtzds/p/7892600.html