比赛时没抓住重点，对那个受限制的“分数求和”太过关心了。。其实如果先利用莫比乌斯函数的一个性质把后面那个[gcd(i,j)=1]去掉，那么问题就可以简化很多。公式如下
这和之前做过的一道题很相似。。（见http://www.cnblogs.com/Just--Do--It/p/7326572.html）
这个式子显然是可以用分块+预处理mu[i]前缀和的方法来做。
预处理复杂度是O(n)，分块解决单组询问复杂度是O(sqrt(n))
求g[n]可以用递推式来解决。
对比g[n]和g[n-1]，可以发现，当i整除n-1时，n/i比(n-1)/i大1，另外，g[n]比g[n-1]多末尾一项n/n（此处“/”即向上取整的除，因为我太懒了，就不写那么标准了。。），由此可以找到规律，g[n]=g[n-1]+d[n-1]+1。（很巧，那道题也用到了d[n]）
代码如下
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod=1e9+7; const int maxn=1e6+5; int prime[maxn+5]; bool check[maxn+5]; int d[maxn+5]; int mu[maxn+5]; int sum[maxn+5]; int min_prime_cnt[maxn+5]; int g[maxn+5]; void init() { mu[1]=1,d[1]=1; int tot=0; for(int i=2; i<=maxn; i++) { if(!check[i]) { prime[tot++]=i; mu[i]=-1; min_prime_cnt[i]=1; d[i]=2; } for(int j=0; j<tot; j++) { int t=i*prime[j]; if(t>maxn) break; check[t]=true; if(i%prime[j]==0) { mu[t]=0; min_prime_cnt[t]=min_prime_cnt[i]+1; d[t]=d[i]/(min_prime_cnt[i]+1)*(min_prime_cnt[t]+1); break; } else { mu[t]=-mu[i]; d[t]=d[i]*2; min_prime_cnt[t]=1; } } } g[1]=1; for(int i=2;i<=maxn;i++) g[i]=(g[i-1]+d[i-1]+1)%mod; for(int i=1;i<=maxn;i++) g[i]=(g[i]+g[i-1])%mod; for(int i=1;i<=maxn;i++) sum[i]=sum[i-1]+mu[i]; } int n; int main() { init(); while(~scanf("%d",&n)) { LL ans=0; for(int i=1, last; i<=n; i=last+1) { last=n/(n/i); ans=(ans+(sum[last]-sum[i-1])*g[n/i])%mod; } printf("%lld ",(ans+mod)%mod); } }