NC212176. brz的函数
描述
蒟蒻 最近学习了莫比乌斯函数，由于学到了新东西蒟蒻
感觉很高兴，一旁的神牛
十分不屑，随手丢了一道水题就难住了蒟蒻
……
题目是这样的，神牛 给出一个整数 n，要求蒟蒻计算下面这个式子：
蒟蒻 不会做但是又想知道答案，但是因为十分害怕又不敢询问神牛
，于是他只好向你求助了。
输入描述
第一行一个整数T表示询问数量。
接下来T行每行一个整数n，意义如上所述。
输出描述
输出T行，每行一个整数表示式子的值。
示例1
输入:
1 2
输出:
-1
说明:
C++(clang++11) 解法, 执行用时: 14ms, 内存消耗: 1504K, 提交时间: 2020-11-22 12:27:42
#include<bits/stdc++.h>
using namespace std;
const int nx=5e4+5;
int mb[nx]={0,1},ans[nx],p[nx],cnt;
bool np[nx];
int main(){
for(int i=2;i<=nx;++i){
if(!np[i])p[cnt++]=i,mb[i]=-1;
for(int j=0;j<cnt&&p[j]*i<=nx;++j){
np[i*p[j]]=1;
if(i%p[j]==0)break;
mb[i*p[j]]=-mb[i];
}
}
for(int d=1;d<nx;++d){
int re=0;
for(int l=d;l<nx;l+=d){
re+=mb[l];
int r=min(l+d-1,nx-2);
ans[l]+=mb[d]*re*re;
ans[r+1]-=mb[d]*re*re;
}
}
for(int i=1;i<nx;++i)ans[i]+=ans[i-1];
int t,n;scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",ans[n]);
}
}