題目描述

給出正整數(shù)n和m，區(qū)間[n, m]內(nèi)的“無平方因子”的數(shù)有多少個？整數(shù)p無平方因子當(dāng)且僅當(dāng)不存在 k > 1，使得p是k2 的倍數(shù)。

輸入

第1行：2個整數(shù)n和m (1 <= n <= m <= 10^9, m - n <= 10^7)

輸出

第1行：1個整數(shù)，表示區(qū)間中無平方因子的數(shù)的個數(shù)Cnt

樣例輸入

Copy (如果復(fù)制到控制臺無換行，可以先粘貼到文本編輯器，再復(fù)制)

1 10
樣例輸出
7
提示
樣例說明：在[1,10]中，無平方因子的數(shù)是：1 2 3 5 6 7 10，4和9分別有平方因子2和3
#----------------------------------------------------------------------------------------------#比較容易做，但細(xì)節(jié)需注意：首先，n，m的上限是10^9，于是就呵呵了，顯然就算bool數(shù)組也不可能開這么大（大概要用900多MB），但是，我們機智地發(fā)現(xiàn)：m-n<=10^7，所以，這告訴了我們：最多只需要10^7的數(shù)組即可。那要怎么做？一個字：篩。直接篩平方因子：i從2開始（它已經(jīng)說了k>1），到sqrt(末端)，只要vis[i^2]為0，就代表這個平方因子沒有被篩過，開始往后面篩，j從首端/i/i（可能有點不懂，一會就知道了）開始，直到現(xiàn)在的j倍i^2大于了末端，其間所有的vis[j*i*i]=1，最后，統(tǒng)計從首端到末端的區(qū)間中有多少個vis為0，就是答案了。當(dāng)然，這里有一個比較嚴(yán)重的問題：都說了vis只有10^7大，怎么能存m,n的10^9呢，很簡單：mod 區(qū)間長度 就行了~因為m-n<=10^7，所以是不會有重復(fù)的。
代碼：
#include<cstdio>#include<cmath>bool vis[10000005];int sums(int x,int y){	int sum=0;	int m=(int)sqrt(y+0.5);//精度有時候會抽風(fēng)，這樣保險一點	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因子的數(shù)，是i^2的幾倍			if(j*i*i>=x)//，因為是向下取整的緣，故為了保險，再判斷一次，因為一旦不屬于該區(qū)間的數(shù)被改動了，就會有重復(fù)的問題				vis[j*i*i%(y-x+1)+1]=1;//mod長度，注意不能減去，因為會減成負(fù)數(shù)，就運行錯誤了	for(int i=1;i<=y-x+1;i++)		if(!vis[i])			sum++;//找沒有被更新（篩）到的數(shù)	return sum;}int main(){	int n,m;	scanf("%d%d",&n,&m);	PRintf("%d",sums(n,m));//輸入輸出}                                                                                                                                           By WZY