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

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

題目
略，請看原題

前言

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

想法

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

• 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程

293079 0元 限免

基于 OpenVINO™ 的 AI 视觉应用进阶课

42051 0元 限免

英特尔 OpenCV 初级认证课程

7732 0元 限免