【数论】无平方因子的数

题目描述

给出正整数n和m，区间[n, m]内的“无平方因子”的数有多少个？整数p无平方因子当且仅当不存在 k > 1，使得p是k2 的倍数。

输入

第1行：2个整数n和m (1 <= n <= m <= 10^9, m - n <= 10^7)

输出

第1行：1个整数，表示区间中无平方因子的数的个数Cnt

样例输入

Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)

1 10
样例输出
7
提示
样例说明：在[1,10]中，无平方因子的数是：1 2 3 5 6 7 10，4和9分别有平方因子2和3
#----------------------------------------------------------------------------------------------#比较容易做，但细节需注意：首先，n，m的上限是10^9，于是就呵呵了，显然就算bool数组也不可能开这么大（大概要用900多MB），但是，我们机智地发现：m-n<=10^7，所以，这告诉了我们：最多只需要10^7的数组即可。那要怎么做？一个字：筛。直接筛平方因子：i从2开始（它已经说了k>1），到sqrt(末端)，只要vis[i^2]为0，就代表这个平方因子没有被筛过，开始往后面筛，j从首端/i/i（可能有点不懂，一会就知道了）开始，直到现在的j倍i^2大于了末端，其间所有的vis[j*i*i]=1，最后，统计从首端到末端的区间中有多少个vis为0，就是答案了。当然，这里有一个比较严重的问题：都说了vis只有10^7大，怎么能存m,n的10^9呢，很简单：mod 区间长度 就行了~因为m-n<=10^7，所以是不会有重复的。
代码：
#include<cstdio>#include<cmath>bool vis[10000005];int sums(int x,int y){	int sum=0;	int m=(int)sqrt(y+0.5);//精度有时候会抽风，这样保险一点	for(int i=2;i<=m;i++)		for(int j=x/i/i;j*i*i<=y;j++)//注意，j从x（首端）/i/i开始,就是x/(i^2)，作用是计算第一个大于首端的含i^2因子的数，是i^2的几倍			if(j*i*i>=x)//，因为是向下取整的缘，故为了保险，再判断一次，因为一旦不属于该区间的数被改动了，就会有重复的问题				vis[j*i*i%(y-x+1)+1]=1;//mod长度，注意不能减去，因为会减成负数，就运行错误了	for(int i=1;i<=y-x+1;i++)		if(!vis[i])			sum++;//找没有被更新（筛）到的数	return sum;}int main(){	int n,m;	scanf("%d%d",&n,&m);	PRintf("%d",sums(n,m));//输入输出}                                                                                                                                           By WZY