2019.10.28 CSP%您赛第四场t3
- 2019 年 10 月 28 日
- 筆記
我写不动前两个了。
原谅一下。
____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
【题目描述】
(varphi)函数是数论中非常常用的函数。对于正整数 x，(varphi)(x) 表示不超过 x 的所有正整数
与 x 互质的个数。
现在我们对它进行一次拓展：对于正整数 x,y，定义 (varphi)(x,y) 表示不超过 y 的所有正
整数与 x 互质的个数。
现在我们给定正整数 n 和 m，对于所有不超过 n 的正整数 i，求 (varphi)(i,m)。
【输入格式】
从文件 phi.in 中读入数据。
输入仅一行两个正整数 n 和 m。
【输出格式】
输出到文件 phi.out 中。
输出 n 行，每行一个整数。第 i 行表示 (varphi)(i,m)。
【样例输入】
11 10
【样例输出】
10
5
7
5
8
3
9
5
7
4
10
以上题面。
顺便补一句，以上算法可接受的复杂度是(O(nsqrt n))。
容易知道，我们枚举所有(ileq n)时，时间复杂度是(O(n))。所以对于每个数的判断，我们可接受的复杂度大约是(O(sqrt n))。
考虑原来做过的题类似的做法。对于一个数(i)，与这个数互质的数的本质实际上是不存在与(i)相同的质因子。所以对于每个(i)，我们用(O(sqrt n))的复杂度求出其所有质因子作为预处理；
而对于每一个求出的质因子，任何含有该质因子的数都不能贡献到答案上。但是由于存在同时具有好几个该数质因子的情况，考虑容斥原理：
举个例子，如果一个数有3个质因子，设其为(a_1,a_2,a_3)，则(ans=m-m/a1-m/a2-m/a3+m/a1/a2+m/a2/a3+m/a1/a3-m/a1/a2/a3)。其中$m是最大取值个数。
同理，设一个数有k个质因子，则容易知道：
(ans=m-m/（所有奇数个a_k相乘的可能）+m/（所有偶数个a_k）相乘的可能)。
容易证明。当我们减去所有含有单个质因子的数时，我们多减去了所有严格含有两个质因子的数；再加上严格含有两个质因子的数，又多加了严格含有三个质因子的数；……以此类推，其实是(k)阶维恩图上的容斥原理。
所以我们可以用一个二进制数的每一位代表该质因子是否被选中。若选中了偶数个质因子，则加上；否则减去。
上代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<cmath> #define rep(i,a,n) for(int i=a;i<=n;i++) #define dep(i,n,a) for(int i=n;i>=a;i--) #define int long long using namespace std; int n,m,prime[100050],idx,ans,book_prime[100050],idx1; bool is_prime[100050],book[100050],mark[100050]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f; } signed main() { memset(prime,-1,sizeof prime); n=read(),m=read(); rep(i,1,n) { memset(book,0,sizeof book); memset(mark,0,sizeof mark); ans=m; idx1=0; int temp=i; int qqqqqq=sqrt(i); rep(j,2,qqqqqq) { if(temp%j==0) { book_prime[++idx1]=j; while(temp%j==0) temp/=j; } } if(temp>1) book_prime[++idx1]=temp; int maxn=(1<<idx1)-1; rep(j,1,maxn) { int cnt=0; int tmp=j; int base=1; int mul=1; while(tmp) { if(tmp&1) ++cnt,mul*=book_prime[base]; ++base; tmp>>=1; } if(cnt&1)ans-=m/mul; else ans+=m/mul; } printf("%lldn",ans); } return 0; }
