建站快车凡科,wordpress设置描述词,专注网站搭建的公司,王也天年龄需要将问题分解一下。
我们需要求的是这个立方体从(0,0,0)能看到的点的个数。可是在三个含有(0,0,0)的面上我们没有办法和其他的一起进行分析#xff08;因为含有坐标是0#xff0c;而我们的数论工具都是从1开始的#xff09;#xff0c;所以我们可以将那三个面分开考虑因为含有坐标是0而我们的数论工具都是从1开始的所以我们可以将那三个面分开考虑剩下的就是一个立方体这个立方体中能看到的点的坐标就是gcd(x,y,z)1然后用莫比乌斯反演进行处理。对于那三个面首先是三个坐标轴上我们只能看到三个点剩下的每个面中我们只能看到gcd(x,y)1的点也用莫比乌斯反演处理。
AC代码
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e65;
int prime[MAXN],mobius[MAXN],sum[MAXN];
bool check[MAXN]; int tot;void pre()
{tot0; mobius[1]1; sum[1]1;for(int i2;iMAXN;i){if(!check[i]){prime[tot]i; mobius[i]-1;}for(int j0;jtot prime[j]*iMAXN;j){check[prime[j]*i]true;if(i%prime[j]) mobius[prime[j]*i]-mobius[i];else{mobius[prime[j]*i]0; break;}}sum[i]sum[i-1]mobius[i];}
}int main()
{pre();int T,n;scanf(%d,T);while(T--){ll ans3;scanf(%d,n);int l,r;for(l1;ln;lr1){rn/(n/l);ans(ll)(sum[r]-sum[l-1])*(n/l)*(n/l)*(n/l);ans(ll)(sum[r]-sum[l-1])*(n/l)*(n/l)*3;}printf(%lld\n,ans);}return 0;
}
