UVa : 11876 - N + NOD (N)

数論

問題概要

http://uva.onlinejudge.org/external/118/11876.html

  • N_0 = 1
  • N_i = N_(i-1) + NOD(N_(i-1))

となるような数列があります。
NOD(N)は、Nの約数の個数を返す関数です。
整数A, Bが入力されたとき、A以上B以下の範囲に、この数列の項がいくつあるかを答えなさい。

制約条件

  • テストケース数 < 100000 (明らかに''やばい''です)
  • 1 <= A <= B <= 1000000

アルゴリズム

まず始めに思いついたのがこれ

A以上B以下の項の数 ＝ B以下の項の数ー(A-1)以下の項の数

これは、O(1)で求められます。
テストケースが10万程度であれば大丈夫ということになります。


つまり、「X以下の項の数を表すような配列」をプログラムの始めで生成できれば勝ちです。
この配列は、素直に数列の1項目から純粋に計算していって、作成することができました。（ちょっとタイム心配してたのですが）
NOD(N)は、O(√N)になるように実装しましょう。

プログラム

int cnt[1000002]; //X以下の項の数を表す配列

//xの約数の数を返す関数
int NOD(int x){
  int res = 0;
  for(int i=1;i*i<=x;i++){
    if(x % i == 0){
      res++;
      if(x / i != i) res++;
    }
  }
  return res;
}

int main(){
  //cnt配列生成処理
  int before = 1;
  cnt[1] = 1;
  while(1){
    int now = before + NOD(before);
    if(now > 1000000){
      REP(i,before+1,1000001) cnt[i] = cnt[i-1];
      break;
    }
    REP(i,before+1,now+1) cnt[i] = cnt[i-1];
    cnt[now]++;
    before = now;
  }

  //テストケース処理
  int T; cin>>T;
  REP(SET,1,T+1){
    int a,b;
    cin>>a>>b;
    cout<<"Case "<<SET<<": "<<cnt[b]-cnt[a-1]<<endl;
  }
}