0%

51nod1222 题解 - 最小公倍数计数

题目链接

题意

(和原题意略不一样,反正差不多)求

事实上还可以再缩小求和上限:

三重循环,剩下一层算,草掉就好了……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxN=1000010;
int pri[maxN],mu[maxN],cnt=0;
bool flg[maxN];
void init(){
mu[1]=1;
for(int i=2;i<maxN;i++){
if(!flg[i]) pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&pri[j]*i<maxN;j++){
flg[pri[j]*i]=1;
if(i%pri[j]==0){mu[pri[j]*i]=0;break;}
mu[pri[j]*i]=-mu[i];
}
}
return;
}
ll calc(ll n){
if(!n) return 0;
ll len1=floor(sqrt(n));
ll res=0,tmp=0;
for(ll k=1;k<=len1;k++){
if(mu[k]){
tmp=0;
ll len2=n/(k*k);
for(ll i=1;i*i*i<=len2;i++){
for(ll j=i+1;j*j*i<=len2;j++)
tmp+=(len2/(i*j)-j)*6+3;
tmp+=(len2/(i*i)-i)*3;
tmp++;
}
res+=mu[k]*tmp;
}
}
return res;
}
int T;
ll N;
int main(){
init();
scanf("%d",&T);
while(T--){
scanf("%lld",&N);
printf("%lld\n",calc(N));
}
return 0;
}