给出一个数列({a_i})，限定上界n，对于任意一个位置i，i的Mobius函数值，等于i的倍数的位置上的值，t组询问，给出m，求第m个位置上的值。
解
不难看出为数论问题，现在关键在于建模，于是不不难有
[a_m+a_{2m}+...+a_{[n/m]m}=mu(m)
]
即
[mu(m)=sum_{m|d}^na_d
]
由Mobius反演定理，我们有
[a_m=sum_{m|d}^nmu(d)mu(d/m)=sum_{d=1}^{[n/d]}mu(dm)mu(d)=sum_{d=1}^{[n/d]}mu^2(d)mu(m)(gcd(d,m)==1)
]
由(sum_{i=1}^nmu^2(i))联想容斥原理，采取更改容斥范围的办法解决问题，设(N=[n/m]),于是有
[a_m=sum_{d=1}^{sqrt{N}}mu(d)sum_{d^2|e}^N(gcd(e,m)==1)=
]
[sum_{d=1}^{sqrt{N}}mu(d)sum_{e=1}^{[N/d^2]}(gcd(ed^2,m)==1)
]
因为(d^2)的存在不好反演，考虑提出特判
[a_m=sum_{d=1}^{sqrt{N}}mu(d)(gcd(d,m)==1)sum_{e=1}^{[N/d^2]}(gcd(e,m)==1)=
]
[sum_{d=1}^{sqrt{N}}mu(d)(gcd(d,m)==1)sum_{e=1}^{[N/d^2]}sum_{x|e,x|m}mu(x)=
]
[sum_{d=1}^{sqrt{N}}mu(d)(gcd(d,m)==1)sum_{x|m}mu(x)[frac{N}{d^2e}]
]
容易知道m的约数个数是固定的，于是考虑单独处理出其(mu)值，接下直接枚举式子，不难得知时间复杂度应为(O(sqrt{N}log_2^N+sqrt{N}sigma(m))=O(sqrt{N}sigma(m)))。
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
#define swap(x,y) x^=y^=x^=y
using namespace std;
bool check[50001];
int prime[10000],pt,mu[50001],
ys[2000],ym[2000],yt;
il int Mu(ll);
template<class free>
il void read(free&);
il void prepare(int);
il ll gcd(ll,ll);
int main(){
int lsy;read(lsy),prepare(50000);
ll n,m,i,j,ans1,ans2;
while(lsy--){
read(n),read(m);
n/=m,yt&=0,ans1&=0;
for(i=1;i*i<m;++i)
if(!(m%i))
ys[++yt]=i,ym[yt]=Mu(i),
ys[++yt]=m/i,ym[yt]=Mu(m/i);
if(i*i==m)ys[++yt]=i,ym[yt]=Mu(i);
for(i=1;i*i<=n;++i){
ans2&=0;
if(gcd(i,m)==1)
for(j=1;j<=yt;++j)
ans2+=ym[j]*(n/(i*i)/ys[j]);
ans1+=ans2*mu[i];
}printf("%lld
",ans1*Mu(m));
}
return 0;
}
il ll gcd(ll a,ll b){
while(b)swap(a,b),b%=a;return a;
}
il int Mu(ll n){
ll i;int tot(0);
for(i=2;i*i<=n;++i)
if(!(n%i)){
n/=i;if(!(n%i))return 0;
++tot;
}if(n>1)++tot;
return (tot&1)?-1:1;
}
il void prepare(int n){
ri int i,j;mu[1]=1;
for(i=2;i<=n;++i){
if(!check[i])prime[++pt]=i,mu[i]=-1;
for(j=1;j<=pt&&prime[j]*i<=n;++j){
check[i*prime[j]]|=true;
if(!(i%prime[j]))break;
mu[i*prime[j]]=~mu[i]+1;
}
}
}
template<class free>
il void read(free &x){
x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}