警告：網上的題解都是誤人子弟，看此篇題解之前請將腦海中對其它寫於本題解之前的網上常見題解的印象全部消除之後方可閱讀
此題的數據范圍是10^9 但是10^10一樣可以做 不影響
首先我們可以預處理出1~r以內所有只由2和9構成的⑨數 容易發現最多有1022個
但是其中有一些⑨數是另一些的倍數 比如說a是b的倍數 那麼一個數如果是a的倍數那麼就一定是b的倍數 我們只需要計算b即可 無需計算a 這裡可以剪枝 不剪無妨
處理出不是另一個數的倍數的所有⑨數 最多應該有466個 求區間內這些數的倍數的數的數量 可以開始容斥了
總數=是一個數的倍數的數的數量-是兩個數公倍數的數的數量+是三個數公倍數的數的數量……
比如說枚舉到某n個數的公倍數 就是對這n個數做一下LCM 然後用r/lcm就是1~r以內這n個數的公倍數的個數了
但是2^466枚舉顯然是不可能的 我們發現這466個數大多都比較大 隨便選幾個做一下LCM就爆r了
於是我們選擇搜索 同樣是2^466的復雜度 但是我們可以剪枝 當當前的LCM大於r就剪枝 剪完之後就沒多少了 1s之內完全可以出解
【無腦噴人時間，不喜勿視】
TM網上的題解尼瑪寫的都是什麼**玩應！！！誰TM說篩出來只有30個！！你們TM也不看看自己篩的是質數麼！！！真要是只有30個你們為何不打表？？？
知不知道你們的**題解誤導了多少人！！連a整除b時誰是誰的倍數都搞不清楚還來指導別人？！！能寫出【if(!a[j]%a[i])】這種東西是完全沒寫過數論麼？？？
真是……以前刷容斥原理的時候就看到這道題 看了題解簡直不知所雲 卡了我很久
在題解完全離譜的情況下還能把代碼寫的八九不離十真是服了
#include#include #include #include #define MAX 1000000000ll using namespace std; long long l,r,ans,a[1050],b[1050]; bool v[1050]; void DFS1(long long x) { if(x>r) return; a[++a[0]]=x; DFS1(x*10+2); DFS1(x*10+9); } void DFS2(int pos=1,int flag=-1,long long now=1) { if(!b[pos]) { if(now^1) ans+=(r/now-(l-1)/now)*flag; return ; } DFS2(pos+1,flag,now); long long temp=now*b[pos]/__gcd(now,b[pos]); if(temp>r) return ; DFS2(pos+1,-flag,temp); } int main() { int i,j,cnt=0; cin>>l>>r; DFS1(2);DFS1(9); sort(a+1,a+a[0]+1); for(i=1;a[i];i++) for(j=i+1;a[j];j++) if(a[j]%a[i]==0) v[j]=1; for(i=1;a[i];i++) if(!v[i]) b[++b[0]]=a[i]; DFS2(); cout<
