Description
在XYZ的dzy loves math6问世后，dzy一直觉得这道题答案太大，一点都不优美，于是他随手在外面套上一个μ。同时，他又觉得输入两个数实在太麻烦，于是题目变成了
，你能解决这个问题吗？
Input
第一行一个整数T表示询问组数，接下来T行每行一个整数n。
Output
对于每一个询问输出一行表示答案
Sample Input
1
2
Sample Output
0
Solution
喜闻乐见的卡常题。
可以很显然的发现(gcd(i,j))必然为(1)，否则对答案无贡献，所以原式化为：
[egin{align}
&sum_{i=1}^{n}sum_{j=1}^imu(i)mu(j)[gcd(i,j)=1]\
=&sum_{i=1}^{n}sum_{j=1}^imu(i)mu(j)sum_{t|i,t|j}mu(t)\
=&sum_{i=1}^nmu(i)sum_{t|i}mu(t)sum_{j=1}^{i/t}mu(jt)
end{align}
]
把后面那坨设为(s)：
[s(i,t)=sum_{j=1}^{i/t}mu(jt)
]
把式子写下来：
[ans=sum_{i=1}^nmu(i)sum_{t|i}mu(t)s(i,t)
]
注意到(s)很显然可以满足这样一个式子：
[s(i,t)=s(i-1,t)+[t|i]mu(i)
]
那么我们可以直接离线询问，对询问排序，然后暴力枚举(i)，显然若(mu(i) e 0)则(i)为(square~free)数，根据数据范围可得(i)的质因子最多只有(9)个，然后直接对(i)(O(2^9))的爆搜约数，顺便更新答案和(s)就好了。
然后这题复杂度很高...常数写小点才能过。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
#define lf double
#define ll long long
const int maxn = 1e7+10;
const int inf = 1e9;
const lf eps = 1e-8;
int mu[maxn],pri[maxn],vis[maxn],tot,s[maxn],n,mn[maxn];
struct data {int v,id,ans;}a[1010];
int cmp(data aa,data b) {return aa.v<b.v;}
int cmp_id(data aa,data b) {return aa.id<b.id;}
void sieve() {
mu[1]=1;
for(int i=2;i<maxn;i++) {
if(!vis[i]) pri[++tot]=i,mu[i]=-1,mn[i]=i;
for(int j=1;j<=tot&&i*pri[j]<maxn;j++) {
vis[i*pri[j]]=1;mn[i*pri[j]]=pri[j];
if(i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
}
int sta[20],top;
int dfs(int x,int v,int i) {
if(v==top+1) return mu[x]*(s[x]+=mu[i]); //x|i必然成立，所以不用判了，取模运算很慢
return dfs(x,v+1,i)+dfs(x*sta[v],v+1,i);
}
int main() {
sieve();read(n);for(int i=1;i<=n;i++) read(a[i].v),a[i].id=i;
sort(a+1,a+n+1,cmp);int p=1,ans=0;
for(int i=1;i<=a[n].v;i++) {
int res=0;
if(mu[i]) {
top=0;for(int x=i;x!=1;x/=mn[x]) sta[++top]=mn[x]; //少除几次..然后快了5s
res=dfs(1,1,i);
}
ans+=res*mu[i];
while(i==a[p].v) a[p].ans=ans,p++;
}sort(a+1,a+n+1,cmp_id);
for(int i=1;i<=n;i++) write(a[i].ans);
return 0;
}