一道更比一道毒瘤

[51 nod 1227] 平均最小公倍数

其实就是求

\[ans=Ans(b)-Ans(a-1) \]

因此我们只需要求出函数\(Ans(n)\)就行了

\[Ans(n)=\sum_{i=1}^n\frac{1}{i}\sum_{j=1}^ilcm(j,i) \]

\[=\sum_{i=1}^n\frac{1}{i}\sum_{j=1}^i\frac{ji}{gcd(j,i)} \]

\[=\sum_{i=1}^n\sum_{j=1}^i\frac{j}{gcd(j,i)} \]

\[=\sum_{i=1}^n\sum_{j=1}^i\sum_{d=1}[gcd(i,j)==d]\frac{j}{d} \]

\[=\sum_{d=1}^n\frac{1}{d}\sum_{d|i}^n\sum_{d|j}^i[gcd(i,j)==d]j \]

\[=\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^i[gcd(i,j)==1]j \]

\[=\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^i\sum_{k|i,k|j}\mu(k)j \]

设

\[F(n)=\sum_{i=1}^n\sum_{k|i,k|n}\mu(k)i \]

\[F(n)=\sum_{k|n}\mu(k)k\sum_{i=1}^{\frac{n}{k}}i \]

\[F(n)=\sum_{k|n}\mu(k)k(1+\frac{n}{k})\frac{n}{k}\frac{1}{2} \]

\[F(n)=\frac{1}{2}\sum_{k|n}\mu(k)(1+\frac{n}{k})n \]

\[F(n)=\frac{1}{2}(\sum_{k|n}\mu(k)n+\sum_{d|n}\mu(k)n\frac{n}{k}) \]

而我们知道

\[\sum_{k|n}\mu(k)n=[n==1] \]

我们也知道

\[\sum_{d|n}\mu(k)\frac{n}{k}=\mu*id=\varphi \]

其中\(*\)表示狄利克雷卷积
因此变成

\[F(n)=\frac{1}{2}(e+n\varphi(n)) \]

带进整个式子

\[=\frac{1}{2}\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}(e+i\varphi(i)) \]

考虑把\(e\)拆出来，那么只有\(i\)等于1是会有贡献，一共有n个1，所以总贡献是n

\[=\frac{1}{2}(n+\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}i\times \varphi(i)) \]

问题转化为求\(i\times \varphi(i)\)的前缀和，我们考虑卷上一个\(id(n)=n\),化简可以得到\(n^2\)，上杜教筛就行了

\[S(n)=\sum_{i=1}^nn^2-\sum_{i=2}^niS(n/i) \]

复杂度\(O(n^{\frac{2}{3}})\)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
typedef long long LL;
const LL mod = 1e9+7;
LL phi[N];
LL f[N];
int v[N],prime[N],tot=0;
LL Pow(LL a,LL b)
{
	LL res=1;
	while(b)
	{
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
LL inv6=Pow(6,mod-2);
LL inv2=Pow(2,mod-2);
LL sqr(LL n)
{
	n%=mod;
	return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
LL sum(LL n)
{
	return 1ll*(1+n)*n%mod*inv2%mod;
}
void init(int n)
{
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!v[i])
		{
			v[i]=i;
			prime[++tot]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=tot;j++)
		{
			if(prime[j]>v[i]||i*prime[j]>n) break;
			v[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
	for(int i=1;i<=n;i++)
	phi[i]=(phi[i-1]+phi[i]*i%mod)%mod;
}
unordered_map<LL,LL> s,vis;
LL Sum(LL n)
{
	if(n<=1e6) return phi[n];
	if(vis[n]) return s[n];
	LL res=sqr(n);
	LL l=2,r;
	for(;l<=n;l=r+1)
	{
		r=(n/(n/l));
		res=(res-(sum(r)-sum(l-1)+mod)%mod*Sum(n/l)%mod+mod)%mod;
	}
	vis[n]=1;
	s[n]=res;
	return res;
}
LL calc(LL n)
{
	LL res=n;
	LL l=1,r;
	for(;l<=n;l=r+1)
	{
		r=n/(n/l);
		res=(res+1ll*(r-l+1)%mod*Sum(n/l)%mod)%mod;
	}
	return res*inv2%mod;	
}
int main()
{
	freopen("minave.in","r",stdin);
	freopen("minave.out","w",stdout);
	init(1e6);
	LL a,b;
	cin>>a>>b;
	cout<<(calc(b)-calc(a-1)+mod)%mod;
	return 0;
} 

SP20173 DIVCNT2 - Counting Divisors (square)

考虑先分析\(\sigma(n^2)\)的性质
显然这是一个积性函数，我们考虑从每一个质因子分别考虑
\(\sigma((p^k)^2)=2*k+1=k+(k+1)=\sigma(p^k)+\sigma(p^{k-1})\)
我们继续观察，\(p^k\)?\(p^{k-1}\)?
也就是\(p_k\)除以他们的质因子的次幂是0或1
那么有没有什么是和指数相关的的呢？
没错,就是\(\mu\)，但是\(\mu\)有负数，怎么办呢
没错，加个平方就行了
事实上和我们分析的一样，\(\sigma(n^2)=\sum_{d|n}\sigma(d)\mu^2(\frac{n}{d})\)

当然和\(\sigma(n^2)=\sum_{d|n}\sigma(\frac{n}{d})\mu^2(d)\)是一样的

\[ans=\sum_{i=1}^n\sum_{d|n}\sigma(\frac{i}{d})\mu^2(i) \]

莫反一下

\[ans=\sum_{d=1}^n\mu^2(d)\sum_{d|i}\sigma(\frac{i}{d}) \]

\[ans=\sum_{d=1}^n\mu^2(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sigma(i) \]

这个东西可以用整除分块做一下，现在的问题变为得到
\(\mu^2(n)\)和\(\sigma(n)\)的前缀和
根据一些容斥的知识，我们可以得到
\(\sum_{i=1}^n\mu^2(i)=\sum_{i=1}^{\sqrt n}\mu(i)\lfloor \frac{n}{d^2}\rfloor\)
这个可以用整除分块做到\(O(\sqrt n)\)
而有一个众所众知的式子
\(\sum_{i=1}^n\sigma(i)=\sum_{i=1}^n\lfloor \frac{n}{i}\rfloor\)
证明的话就是考虑计算每个数在n个数中有多少倍数
这个也可以整除分块做到\(O(\sqrt n)\)
不过两个\(n\)套起来就是\(O(n)\)了
我们考虑先预处理\(\mu^2(n)\)和\(\sigma(n)\)的前\(n^{\frac{2}{3}}\)项的前缀和，询问的时候直接调用
复杂度和杜教筛类似是\(O(n^{\frac{2}{3}})\)
当然，这个题有毒
它的\(n\)是\(10^{12}\),预处理要处理到\(10^8\)
因此不仅空间大，常数也大
这份代码在SPOJ上并不能跑过

#include<bits/stdc++.h>
using namespace std;
const int N = 5e7+5;
const int M = 1e7+7;
typedef long long LL;
LL d[N];
int mu[N];
int t[N];
bool v[N];
int prime[M],tot=0;
void init(int n)
{
	mu[1]=1;
	d[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!v[i])
		{
			v[i]=1;
			prime[++tot]=i;
			d[i]=2;
			mu[i]=-1;
			t[i]=2;
		}
		for(int j=1;j<=tot;j++)
		{
			if(i*prime[j]>n) break;
			v[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				t[i*prime[j]]=t[i]+1;
				d[i*prime[j]]=d[i]/t[i]*(t[i]+1);
				mu[i*prime[j]]=0;
				break;
			}
				t[i*prime[j]]=2;
				d[i*prime[j]]=d[i]*d[prime[j]];
				mu[i*prime[j]]=mu[i]*mu[prime[j]];
		}
	}
	for(int i=1;i<=n;i++)
	{
		d[i]+=d[i-1];
		t[i]=t[i-1]+abs(mu[i]);
	}
}
LL R;
LL SumU(LL n)
{
	if(n<=R) return t[n];
	LL res=0;
	for(LL i=1;i*i<=n;i++)
	res=(res+mu[i]*(n/i/i));
	return res;
}
LL SumD(LL n)
{
	if(n<=R) return d[n];
	LL res=0;
	LL l=1,r;
	for(;l<=n;l=r+1)
	{
		r=n/(n/l);
		res=res+(r-l+1)*(n/l);		
	}
	return res;
}
void solve(LL n)
{
	LL res=0;
	LL l=1,r;
	LL last=0;
	LL m=sqrt(n);
	for(LL i=1;i<=m;i++)
	if(mu[i]!=0) res=res+SumD(n/i);
	l=m+1;last=SumU(m);
	for(;l<=n;l=r+1)
	{
		r=n/(n/l);
		LL now=SumU(r);
		res=(res+(now-last)*SumD(n/l));
		last=now;
	}
	printf("%lld\n",res);
}
LL a[20000];
LL INF = 1e12;

int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	int T;
	cin>>T;
	LL r;
	for(int i=1;i<=T;i++)
	{
		scanf("%lld",&a[i]);
		r=max(r,a[i]);	
	}
	if(r<=10000) R=10000;
	else R=N-10;
	init(R);
	for(int i=1;i<=T;i++)
	solve(a[i]);
	return 0;
}

[51nod1222]最小公倍数计数

还是先做成前缀相减的形式
问题转化为求

\[F(n)=\sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)\leq n] \]

\[F(n)=\sum_{i=1}^n\sum_{j=1}^n\sum_{d|i,d|j}[gcd(i,j)==d][\frac{ij}{d}\leq n] \]

\[=\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}[gcd(i,j)==1][ij\leq \frac{n}{d}] \]

\[=\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{k|i,k|j}\mu(k)[ij\leq \frac{n}{d}] \]

\[=\sum_{d=1}^n\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor }\mu(k)\sum_{i=1}^{\lfloor \frac{n}{dk} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{dk}\rfloor}[ijk^2\leq \frac{n}{d}] \]

\[=\sum_{k=1}^n\mu(k)\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor }\sum_{i=1}^{\lfloor \frac{n}{dk} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{dk}\rfloor}[ijd\leq \frac{n}{k^2}] \]

发现\(k\)最大不会超过\(\sqrt(n)\)
因此

\[=\sum_{k=1}^{\sqrt(n)}\mu(k)\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor }\sum_{i=1}^{\lfloor \frac{n}{dk} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{dk}\rfloor}[ijd\leq \frac{n}{k^2}] \]

可以考虑枚举\(k\)，计算后面的值
观察后三项的上指标
会发现，如果\(a\geq \lfloor \frac{n}{k} \rfloor\),后面的式子就为0
类似的，\(i,j\)的上指标都可以被后面的约束掉
因此，后边部分等于

\[\sum_{d}\sum_{i}\sum_{j}[ijk\leq\frac{n}{k}] \]

我们考虑强制让\(d\leq i \leq j\) 然后乘一个系数就行了
考虑不同的\(d,i,j\)的状态
1：\(d,d,d\)，即三个相等，枚举到的合法的d就加一就行了
2：\(d,i,i\)，即后两个相等，算出合法的\(d,i\)的数量乘以3
3：\(d,d,i\) 与2类似
4：\(d,i,j\)
发现\(d\)只需要枚举到n的三次根就行了，i只需要枚举到n的平方根就行了
总复杂度与杜教筛类似为\(O(n^{\frac{2}{3}})\),它的系数是6
可以再计算后面的时候一块计算

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N =1e6+7;
LL mu[N],v[N];
LL prime[N],tot=0;
void init(LL n)
{
	mu[1]=1;
	for(LL i=2;i<=n;i++)
	{
		if(!v[i])
		{
			v[i]=i;
			mu[i]=-1;
			prime[++tot]=i;
		}
		for(LL j=1;j<=tot;j++)
		{
			if(prime[j]>v[i]||i*prime[j]>n) break;
			v[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=mu[i]*mu[prime[j]];
		}
	}
}
LL S(LL n)
{
	LL res=0;
	for(LL k=1;k*k<=n;k++)
	{
		if(!mu[k]) continue;
		LL cnt=0;
		LL limit=n/(k*k);
		for(LL i=1;i*i*i<=limit;i++)
		{
			for(LL j=i+1;i*j*j<=limit;j++)
			cnt+=(LL)(limit/(i*j)-j)*6+3;//i,j,k+i,j,j 
			cnt+=(LL)(limit/(i*i)-i)*3;//i,i,j
			cnt++;//i,i,i
		}
		res=res+mu[k]*cnt;
	}
	return (res+n)/2;
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	init(1e6);
	LL l,r;
	cin>>l>>r;
	cout<<S(r)-S(l-1);
	return 0;
}

[51nod1220] 约数之和

求

\[\sum_{i=1}^n\sum_{j=1}^n\sigma(ij) \]

其中\(\sigma(n)\)表示\(n\)的因子之和
首先有引理
\(\sigma(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\frac{xj}{y}\)
证明与SDOI约数个数和类似，不赘述了
直接莫反

\[\sum_{i=1}^n\sum_{j=1}^n\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\frac{xj}{y} \]

\[\sum_{x=1}^nx\sum_{y=1}^n\sum_{i=1}^{\lfloor \frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{y}\rfloor}[gcd(x,y)==1]j \]

\[\sum_{x=1}^nx\sum_{y=1}^n[gcd(x,y)==1]\lfloor \frac{n}{x}\rfloor\sum_{j=1}^{\lfloor \frac{n}{y}\rfloor}j \]

\[\sum_{x=1}^nx\sum_{y=1}^n\sum_{d|x,d|y}\mu(d)\lfloor \frac{n}{x}\rfloor\sum_{j=1}^{\lfloor \frac{n}{y}\rfloor}j \]

\[\sum_{d=1}^n\mu(d)d\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}x\sum_{y=1}^{\lfloor \frac{n}{d}\rfloor}\lfloor \frac{n}{dx}\rfloor\sum_{j=1}^{\lfloor \frac{n}{dy}\rfloor}j \]

\[\sum_{d=1}^n\mu(d)d\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}x\lfloor \frac{n}{dx}\rfloor\sum_{y=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{dy}\rfloor}j \]

设\(f(n)=\sum_{i=1}^n\sum_{j=1}^{\lfloor \frac{n}{i}\rfloor}i\),\(g(n)=\sum_{i=1}^ni\lfloor \frac{n}{i} \rfloor\)

\[ans=\sum_{d=1}^n\mu(d)d\times g(\lfloor \frac{n}{d}\rfloor)f(\lfloor \frac{n}{d}\rfloor) \]

考虑\(f(n)\)和\(g(n)\)的关系
会发现，\(g(n)\)其实就是把\(f(n)\)中每个数\(i\)的权值乘上他出现的次数
因此两个式子是等价的，问题进一步转化为

\[ans=\sum_{d=1}^n\mu(d)d\times g(\lfloor \frac{n}{d}\rfloor)^2 \]

我们只需要求出\(g(n)\)的前缀和就可以整除分块了
接着会发现\(\sum_{i=1}^n\sigma(i)=\sum_{i=1}^ni\lfloor \frac{n}{i} \rfloor=g(n)\)
因此\(g(n)=\sum_{i=1}^n\sigma(i)\)
众所众知，\(\sigma(n)\)是积性函数，可以线性筛求出来
类似于杜教筛，预处理除\(n^{\frac{2}{3}}\)的前缀和，剩下的整除分块暴力做，可以做到\(O(n^{\frac{2}{3}})\)
别忘了最后还剩一个\(\mu(d)d\)，卷上一个\(id(n)=n\),就可以杜教筛了

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
typedef long long LL;
int mu[N];
LL f[N];
int v[N],prime[N],tot=0;
const int mod = 1e9+7;
LL d[N],t[N],g[N];
void init(LL n)
{
	mu[1]=1;
	d[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!v[i])
		{
			v[i]=i;
			prime[++tot]=i;
			mu[i]=-1;
			d[i]=i+1;
			g[i]=i;
			t[i]=i+1;
		}
		for(int j=1;j<=tot;j++)
		{
			if(prime[j]>v[i]||i*prime[j]>n) break;
			v[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
			{
				g[i*prime[j]]=g[i]*prime[j];
				t[i*prime[j]]=t[i]+g[i*prime[j]];
				d[i*prime[j]]=d[i]/t[i]*t[i*prime[j]];
				mu[i*prime[j]]=0;
				break;
			}
			else 
			{
				mu[i*prime[j]]=mu[i]*mu[prime[j]];
				d[i*prime[j]]=d[i]*d[prime[j]];
				g[i*prime[j]]=prime[j];
				t[i*prime[j]]=1+prime[j];
			}
		} 
	}
	for(int i=1;i<=n;i++)
	{
		f[i]=(f[i-1]+mu[i]*i%mod+mod)%mod;
		d[i]=(d[i]+d[i-1])%mod;
	}
}
unordered_map<LL,LL> vis,s;
LL Sum(LL n)
{
	if(n<=1e6) return f[n];
	if(vis[n]) return s[n];
	LL res=1;
	LL l=2,r;
	for(;l<=n;l=r+1)
	{
		r=n/(n/l);
		res=(res-1ll*(l+r)*(r-l+1)/2%mod*Sum(n/l)%mod+mod)%mod;
	}
	vis[n]=1;
	s[n]=res;
	return res;
}
LL D(LL n)
{
	if(n<=1e6) return d[n];
	LL l=1,r;
	LL res=0;
	for(;l<=n;l=r+1)
	{
		r=n/(n/l);
		res=(res+(l+r)*(r-l+1)/2%mod*(n/l)%mod)%mod;
	}
	return res;
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	init(1e6);
	LL n;
	cin>>n;
	LL res=0;
	LL l=1,r;
	for(;l<=n;l=r+1)
	{
		r=n/(n/l);
		LL val=D(n/l);
		res=(res+(Sum(r)-Sum(l-1)+mod)%mod*val%mod*val%mod)%mod;
	}
	cout<<res;
	return 0;
}

[51nod1584]加权约数和

求

\[\sum_{i=1}^n\sum_{j=1}^nmax(i,j)\sigma(ij) \]

我们知道这个\(n*n\)的答案矩阵是对称的，因此答案即为

\[2\sum_{i=1}^n\sum_{j=1}^ii\sigma(ij)-\sum_{i=1}^n\sigma(i^2) \]

先看前半部分
和上一题类似
\(\sigma(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\frac{xj}{y}\)
带进式子

\[\sum_{i=1}^ni\sum_{j=1}^i\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\frac{xj}{y} \]

\[\sum_{i=1}^ni\sum_{j=1}^i\sum_{x|i}x\sum_{y|j}\sum_{d|x,d|y}\mu(d)\frac{j}{y} \]

\[\sum_{d=1}^n\mu(d)d\sum_{i=1}^{\lfloor\frac{n}{d} \rfloor}i\sum_{x|i}xd\sum_{j=1}^i\sum_{y|j}\frac{j}{y} \]

\[\sum_{d=1}^n\mu(d)d\sum_{i=1}^{\lfloor\frac{n}{d} \rfloor}i\sum_{x|i}xd\sum_{j=1}^i\sum_{y|j}y \]

\[\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{\lfloor\frac{n}{d} \rfloor}i\sigma(i)\sum_{j=1}^i\sigma(j) \]

设\(f(n)=n\sigma(n)\sum_{i=1}^n\sigma(i)\)

\[ans=\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{\lfloor\frac{n}{d} \rfloor}f(i) \]

我们可以预处理除\(\sigma(n)\)的前缀和，这样就能快速计算\(f(i)\)
但是询问的次数非常多，需要我们\(O(1)\)回答
因此继续化简

\[ans=\sum_{T=1}^n\sum_{k|T}\mu(k)k^2f(\frac{T}{k}) \]

这个式子可以通过调和级数\(O(n\log n)\)的算出来，再计算前缀和就可以\(O(1)\)查询了
接着看后半部分
问题是处理\(\sigma(n^2)\)的前缀和
这个也是可以用线性筛筛出来的，毕竟这是一个积性函数

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 1e6+7;
const LL mod =1e9+7; 
LL d[N],t[N],p[N];
LL sd[N],st[N],sp[N];
LL s[N],g[N];
LL mu[N];
LL v[N],prime[N],tot=0;
LL Pow(LL a,LL b)
{
	LL res=1;
	while(b)
	{
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
LL inv(LL n)
{
	return Pow(n,mod-2);
}
LL f[N];
void init(LL n)
{
	mu[1]=1;
	sd[1]=1;
	d[1]=1;
	for(LL i=2;i<=n;i++)
	{
		if(!v[i])
		{
			v[i]=i;
			prime[++tot]=i;
			mu[i]=-1;
			d[i]=i+1;
			t[i]=i+1;
			p[i]=i;
			sd[i]=(1+i+(LL)i*i%mod)%mod;
			st[i]=(1+i+(LL)i*i%mod)%mod;
			sp[i]=(LL)i*i%mod;
		}
		for(LL j=1;j<=tot;j++)
		{
			if(v[i]<prime[j]||i*prime[j]>n) break;
			LL k=i*prime[j];
			v[i*prime[j]]=prime[j];
			if(i%prime[j]==0)
			{
				mu[k]=0;
				p[k]=p[i]*prime[j]%mod;
				t[k]=(t[i]+p[k])%mod;
				d[k]=d[i]*inv(t[i])%mod*t[k]%mod;
				sp[k]=sp[i]*prime[j]%mod*prime[j]%mod;
				st[k]=(st[i]+sp[i]*prime[j]%mod+sp[k])%mod;
				sd[k]=(sd[i]*inv(st[i])%mod*st[k])%mod;
				break;
			}
			else
			{
				mu[k]=mu[i]*mu[prime[j]];
				p[i*prime[j]]=prime[j];
				t[i*prime[j]]=1+prime[j];
				d[i*prime[j]]=d[i]*d[prime[j]]%mod;
				sp[i*prime[j]]=prime[j]*prime[j]%mod;
				st[i*prime[j]]=(1+prime[j]+prime[j]*prime[j]%mod)%mod;
				sd[i*prime[j]]=sd[i]*sd[prime[j]]%mod;
			}
		}
	}
	for(LL i=1;i<=n;i++)
	s[i]=(d[i]+s[i-1])%mod;
	for(LL i=1;i<=n;i++)
	sd[i]=(sd[i-1]+i*sd[i]%mod)%mod;
	for(LL i=1;i<=n;i++)
	g[i]=1ll*i*d[i]%mod*s[i]%mod;
	for(LL d=1;d<=n;d++)
	for(LL T=d;T<=n;T+=d)
	f[T]=(f[T]+mu[d]*d%mod*d%mod*g[T/d]%mod+mod)%mod;
	for(LL i=1;i<=n;i++)
	f[i]=(f[i-1]+f[i])%mod;
}
LL calc(LL n)
{
	return (2ll*f[n]%mod-sd[n]+mod)%mod;
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	init(1e6);
	LL T;
	cin>>T;
	int ca=0;
	while(T--)
	{
		LL n;
		ca++;
		scanf("%lld",&n);
		printf("Case #%d: %lld\n",ca,calc(n));
	}
	return 0;
}