TOJ 235 默比烏斯問題

TOJ 235 默比烏斯問題

題目概述:

有個函數叫做Mobius funtion，翻譯很多種(默比烏斯,梅比斯.....) 。

給L,R，求|f(L)|+|f(L+1)|+.....+|f(R-1)|+|f(R)|。

思路:

其實Mobius funtion出來不是0就是1不然就是-1，那絕對值之後不是0就是1，所以就可以直接用布林陣列來存。

這題的難點是如果L~R每一個都去質因數分解之類的太慢，然後數值範圍又是int上限，沒辦法開那麼大的陣列來做篩選。

但注意R-L<=300000，其實我們可以開300000大小的陣列，接著將L~R的含數值存在(L-L)~(R-L)。

然後還有一點值得注意的是，我們不需要篩選樹值範圍內的所以完全平方數，而只要篩選平方根為質數的完全平方數就行了!因為平方根為質數的完全平方數 一定是 平方根為非質數的完全平方數 的因數(像是4(22)為16(42)的因數)。

//By SCJ

//TOJ 235

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

vector<int> sq;

bool np[46342];

bool a[300005];

main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   for(int i=2;i<46341;++i){

       if(!np[i]){

           sq.push_back(i*i);

           for(int j=i+i;j<46341;j+=i) np[j]=1;

       }

   }

   int T;cin>>T;

   while(T--)

   {

       memset(a,0,sizeof(a));

       int l,r,ans=0;cin>>l>>r;

       for(int i=0;i<sq.size();++i)

           for(int j=sq[i]*(ceil((double)l/sq[i]));j<=r;j+=sq[i]) a[j-l]=1;

       for(int i=l;i<=r;++i) ans+=a[i-l];

       cout<<r-l-ans+1<<endl;

   }

}