Codeforce 111 B. Petya and Divisors 解析(思維)

今天我們來看看CF111B
題目連結

題目
略，請看原題

前言

看了別人的解答就豁然開朗

想法

因為如果真的每個數字都檢查一遍，複雜度會輕鬆超越$O(n^2)$，因此會想到要對$i$前面的$index$做一些預處理。但是如果儲存$1\sim i-1$的$x$的$l.c.m.$，數字很有可能會到$10^{(10^5)}$的量級，實在太大了。
這題我們可以儲存每個因數「最後出現」在哪個$index$，那麼對於每個$i$，只要枚舉$x_i$有哪些因數，並且看看那個因數有沒有出現在$i-y_i\sim i-1$就好。
複雜度:$O(n\sqrt{n})$，$\sqrt{n}$是因為要枚舉因數。

程式碼:

const int _n=1e5+10;  
int t,n,x,y,show[_n];  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n;rep(i,1,n+1){  
    cin>>x>>y;  
    int hf=sqrt(x),cnt=0;rep(j,1,hf+1)if(x%j==0){  
      t=x/j;  
      if(show[j]<i-y)cnt++;  
      if(t!=j and show[t]<i-y)cnt++;  
      show[j]=i,show[t]=i;  
    }  
    cout<<cnt<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission