情之所至,甘之如饴

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
#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn=10010000;
int mu[maxn],prime[maxn],cnt;
bool not_prime[maxn];
inline void Get_Mu(int n) {
mu[1]=1;
for(int i=2;i<=n;i++) {
if(!not_prime[i]) prime[++cnt]=i,mu[i]=-1;
for(int j=1;prime[j]*i<=n;j++) {
not_prime[prime[j]*i]=1;
if(i%prime[j]==0) {
mu[prime[j]*i]=0;
break;
}
mu[prime[j]*i]=-mu[i];
}
}
}
int main() {
cin>>n;
Get_Mu(n);
for(int i=1;i<=n;i++) cout<<mu[i]<<' ';
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:726.4k