专栏首页数据结构与算法线性筛莫比乌斯函数

线性筛莫比乌斯函数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define lli long long int 
 6 using namespace std;
 7 const int MAXN=10000001;
 8 void read(int &n)
 9 {
10     char c='+';int x=0;bool flag=0;
11     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     x=(x<<1)+(x<<3)+c-48,c=getchar();
14     flag==1?n=-x:n=x;
15 }
16 int n,m;
17 bool check[MAXN];
18 int prime[MAXN];
19 int mu[MAXN];
20 int tot=0;
21 int  main()
22 {
23            cin>>n;
24            mu[1]=1;
25         for(int i=2;i<=n;i++)
26         {
27             if(!check[i])
28                 prime[++tot]=i,mu[i]=-1;// 只有i与它互质 
29             for(int j=1;j<=tot;j++)
30             {
31                 if(i*prime[j]>n)
32                     break;
33                 check[i*prime[j]]=1;
34                 if(i%prime[j]==0)
35                 {
36                     mu[i*prime[j]]=0; 
37                     break;
38                 }
39                 else
40                     mu[i*prime[j]]=-mu[i];
41             }
42         }
43         printf("%d\n",mu[n]);
44     return 0;
45 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ2820: YY的GCD(反演)

    \[\sum_{i = 1}^n \frac{n}{k} \frac{n}{k} \sum_{p \in P, p | k} \mu(\frac{K}{p})\...

    attack
  • BZOJ1101: [POI2007]Zap(莫比乌斯反演)

    Description   FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gc...

    attack
  • 洛谷2017 5月月赛R1

    我只想说面对这种难度的题目就是冲着20%的数据暴力。。。 分数:40+20+36.1+38+0+19 T1 签到题 III 题目背景 pj组选手zzq近日学会了...

    attack
  • BZOJ2820: YY的GCD(反演)

    \[\sum_{i = 1}^n \frac{n}{k} \frac{n}{k} \sum_{p \in P, p | k} \mu(\frac{K}{p})\...

    attack
  • BZOJ1101: [POI2007]Zap(莫比乌斯反演)

    Description   FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gc...

    attack
  • 栈缓冲区溢出

    https://baike.baidu.com/item/%E8%8E%AB%E9%87%8C%E6%96%AF%E8%A0%95%E8%99%AB/90359...

    字节脉搏实验室
  • 暑假(补)-6

    优先队列是什么呢?优先队列其实是一种特殊的队列,对队列的元素按照一定的先后顺序,队列自动排序,这就是优先队列。

    AngelNH
  • 洛谷2017 5月月赛R1

    我只想说面对这种难度的题目就是冲着20%的数据暴力。。。 分数:40+20+36.1+38+0+19 T1 签到题 III 题目背景 pj组选手zzq近日学会了...

    attack
  • 51Nod--1001 数组中和等于K的数对

    题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1001

    指点
  • Hackerrank GCD Product(莫比乌斯反演)

    attack

扫码关注云+社区

领取腾讯云代金券