第一发容斥,感觉挺有意思的 →_→
【题目链接】
【题目类型】容斥
&题意:
求(a,b)区间内,与n互质的数的个数。 \(a,b\leq 10^{15}\)
&题解:
分析:我们可以先转化下:用(1,b)区间与n互质的数的个数减去(1,a-1)区间与n互质的数的个数,那么现在就转化成求(1,m)区间于n互质的数的个数,如果要求的是(1,n)区间与n互质的数的个数的话,我们直接求出n的欧拉函数值即可,可是这里是行不通的!我们不妨换一种思路:就是求出(1,m)区间与n不互质的数的个数,假设为num,那么我们的答案就是:m-num!现在的关键就是:怎样用一种最快的方法求出(1,m)区间与n不互质的数的个数?方法实现:我们先求出n的质因子(因为任何一个数都可以分解成若干个质数相乘的),如何尽快地求出n的质因子呢?我们这里又涉及两个好的算法了!第一个:用于每次只能求出一个数的质因子,适用于题目中给的n的个数不是很多,但是n又特别大的; 第二个:一次求出1~n的所有数的质因子,适用于题目中给的n个数比较多的,但是n不是很大的。 本题适用第一个算法!举一组实例吧:假设m=12,n=30.
第一步:求出n的质因子:2,3,5;
第二步:(1,m)中是n的因子的倍数当然就不互质了(2,4,6,8,10)->n/2 6个,(3,6,9,12)->n/3 4个,(5,10)->n/5 2个。
如果是粗心的同学就把它们全部加起来就是:6+4+2=12个了,那你就大错特错了,里面明显出现了重复的,我们现在要处理的就是如何去掉那些重复的了!
第三步:这里就需要用到容斥原理了,公式就是:n/2+n/3+n/5-n/(2* 3)-n/(2* 5)-n/(3* 5)+n/(2* 3* 5).
第四步:我们该如何实现呢?我在网上看到有几种实现方法:dfs(深搜),队列数组,位运算三种方法都可以!上述公式有一个特点:n除以奇数个数相乘的时候是加,n除以偶数个数相乘的时候是减。我这里就写下用队列数组如何实现吧:我们可以把第一个元素设为-1然后具体看代码如何实现吧!
【时间复杂度】O(\(\sqrt{n}\))
&代码:
#includeusing namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;#define cle(a,val) memset(a,(val),sizeof(a))#define SI(N) scanf("%d",&(N))#define SII(N,M) scanf("%d %d",&(N),&(M))#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))#define rep(i,b) for(int i=0;i<(b);i++)#define rez(i,a,b) for(int i=(a);i<=(b);i++)#define red(i,a,b) for(int i=(a);i>=(b);i--)const ll LINF = 0x3f3f3f3f3f3f3f3f;#define PU(x) puts(#x);#define PI(A) cout<<(A)< 1) phi[num++]=n;}ll pie(ll m){ ll que[MAXN],i,j,k,t=0,sum=0; que[t++]=-1; for(i=0;i >T;while(T--) Solve(); return 0;}
转载自: