51nod 1584 權重約數和

去年的 tangjz 非常喜歡做數論題，但是一年以後的 tangjz 卻不那麼會做了。

在整理以前的試題時，他發現了這樣一道題目：“求  ∑σ(i)  ，其中  1≤i≤N  ，  σ(i)  表示  i  的約數之和。” 現在他長大了，題目也變難了，是以麻煩你來幫他解決一道數論題吧。

他需要你求如下表達式的值：

  ∑Ni=1∑Nj=1max(i,j)⋅σ(i⋅j)  

其中  max(i,j)  表示  i  和  j  裡的最大值，  σ(i⋅j)  表示  i⋅j  的約數之和。

例如當  N=2  的時候，由  σ(1)=1,σ(2)=1+2=3,σ(4)=1+2+4=7  可知，答案應為  1⋅σ(1⋅1)+2⋅σ(1⋅2)+2⋅σ(2⋅1)+2⋅σ(2⋅2)=27  。 他發現答案有點大，是以你隻需要告訴他答案模  1000000007  的值即可。

Input

每個測試點含有多組測試資料。
第一行是一個正整數T，表示接下來有T組測試資料。（1≤T≤50000）
接下來的T行，每組測試資料占一行。
每行有一個正整數N，含義如描述所示。（1≤N≤1000000）      

Output

共有T行。對于每組測試資料，輸出一行資訊"Case #x: y"。
其中x表示對應的是第幾組測試資料，y表示相應的答案模1000000007的值。      

Input示例

5
1
2
3
4
5      

Output示例

Case #1: 1
Case #2: 27
Case #3: 162
Case #4: 686
Case #5: 1741






【分析】
經過一番莫比烏斯反演，可以做到O(nlogn)預處理，O(1)查詢
線性篩寫的太垃圾，需要特殊的卡常技巧
代碼隻有一次AC過...趁評測機跑得飛快水過了      

【代碼】
           
    
//51nod 1584 權重約數和
#include<bits/stdc++.h>
#define N 1000000
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mxn=1000001;
const int mod=1e9+7;
int n,m,T;
bool vis[mxn];
int s[mxn],ss[mxn],miu[mxn],pri[mxn];
int ans[mxn],g[mxn],c[mxn];
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x;
}
inline int ksm(int x,int k)
{
    int b=x;--k;
	while(k)
	{
	    if(k&1) x=(ll)x*b%mod;
	    b=(ll)b*b%mod,k>>=1;
	}
	return x;
}
inline int get(int x,int p)
{
	int cnt=0,tmp=x;
	while(tmp%p==0) cnt++,tmp/=p;
	int t=ksm(p,2*cnt+1)-1;
	if(!c[p-1]) c[p-1]=ksm(p-1,mod-2);
	t=(ll)t*c[p-1]%mod;
	return (ll)g[tmp]*t%mod;
}
inline void init()
{
	int i,j;
	miu[1]=g[1]=1;
	fo(i,2,N)
	{
		if(!vis[i])
		  pri[++pri[0]]=i,miu[i]=-1,g[i]=(1+i+(ll)i*i%mod)%mod;
		for(int j=1;j<=pri[0] && (ll)i*pri[j]<=N;j++)
		{
			vis[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				g[i*pri[j]]=get(i*pri[j],pri[j]);
				break;
			}
			miu[i*pri[j]]=-miu[i];
			g[i*pri[j]]=(ll)g[i]*g[pri[j]]%mod;
		}
	}
	for(i=1;i<=N;i++) for(j=i;j<=N;j+=i)
	{
		s[j]=s[j]+i;
		if(s[j]>mod) s[j]-=mod;
	}
	fo(i,1,N)
	{
		ss[i]=(ss[i-1]+s[i])%mod;
		if(ss[i]>mod) ss[i]-=mod;
	}
	for(i=1;i<=N;i++) if(miu[i]) for(j=i;j<=N;j+=i)
	{
	    ans[j]=ans[j]+(ll)i*j*miu[i]%mod*s[j/i]%mod*ss[j/i]%mod;
	    if(ans[j]<0) ans[j]+=mod;
		else if(ans[j]>mod) ans[j]-=mod;
	}
	fo(i,1,N)
	{
		ans[i]=ans[i]+ans[i-1];
		if(ans[i]>mod) ans[i]-=mod;
	}
	fo(i,1,N) g[i]=(ll)i*g[i]%mod;
	fo(i,1,N)
	{
		g[i]=g[i-1]+g[i];
		if(g[i]>mod) g[i]-=mod;
	}
}
int main()
{
	init();
	int i,j;
	T=read();
	fo(i,1,T)
	{
		n=read();
		printf("Case #%d: %d\n",i,(2*ans[n]%mod-g[n]+mod)%mod);
	}
	return 0;
}