题意：( g(k) = 2^{f(k)} ) ，求( sum_{i = 1}^{n} g(i) ),其中( f(k))代表k的素因子个数。
思路：题目意思很简单，但是着重于推导和简化，这是数论题的一贯思路，其中g(k)的方程可以看出是求k的无平方因子的个数，那么题目就是求1~n的无平方因字数的和了。
首先我们可以从莫比乌斯函数入手。
从( mu(d) )的性质有，当d为素数单次连积时( mu(d)=(-1)^k)，其余d不为1时( mu(d)=0)
那么可知( mu^{2}(d) )在d满足条件时一定为正值1，故g(k)可化为( sum_{d | i} mu^{2}(d) ) 且$$ans = sum_{i = 1}^{n}{sum_{d | i} mu^{2}(d)} $$
接下来从容斥方向考虑。其实我们直接枚举素因子连乘的k,那么由(mu(d))函数的性质,可知当存在(k^2 | d)时,(mu(k))是不为0的，这样就去掉了素因子次数大于等于2的d，那么式子又可化成$$ {mu^{2}(d)}= { sum_{k^2|d}{mu(k)} }$$
进一步$${sum_{k=1}^{n}sum_{k^2 | d} {mu(k)}lfloorfrac{n}{d} floor }$$
(lfloorfrac{n}{d} floor)是1~n中被d整除的个数。
其中d为k^2的整倍数。
交换求和符号，将式子化成
$$sum_{k = 1}^{n}{mu(k)}sum_{i=1}^{lfloor frac{n}{k^2} floor} lfloor frac{n}{k^{2} i} floor$$
接着枚举倍数求和就可以了，其中后个求和函数在1e6范围内可以预处理。
/** @Date : 2016-12-04-22.09
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version :
*/
#include<bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e6+20;
const LL mod = 1e9 + 7;
const double eps = 1e-8;
int sum1[N];
int pri[N];
int mu[N];
bool vis[N];
int c = 0;
void mobius()
{
MMF(vis);
mu[1] = 1;
for(int i = 2; i < N; i++)
{
if(!vis[i])
pri[c++] = i, mu[i] = -1;
for(int j = 0; j < c && i * pri[j] < N; j++)
{
vis[i * pri[j]] = 1;
if(i % pri[j])
mu[i * pri[j]] = -mu[i];
else
{
mu[i * pri[j]] = 0;
break;
}
}
}
}
int sum(LL n)//
{
if(n < N && sum1[n])//小于N下且已经处理了直接返回预处理的值
return sum1[n];
LL t = 0;
for(LL i = 1, j = 0; i <= n; i = j + 1)
{
j = n / (n / i);
t += n / i * (j - i + 1);//优化，大于n一半的直接加
}
t %= mod;
if(n >= N)
return t;
else
return sum1[n] = t;
}
int main()
{
int T;
mobius();
while(~scanf("%d", &T))
{
int cnt = 0;
while(T--)
{
LL n;
LL ans = 0;
scanf("%lld", &n);
for(LL i = 1; i <= n / i; i++)//枚举sqrt(n)的因子
if(mu[i])
ans = (ans + sum(n/i/i) * mu[i]) % mod;//注意i取整
printf("Case #%d: %lld
", ++cnt, (ans + mod) % mod);
}
}
return 0;
}