Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2012-08-18

SRM552 Div1 900

| 23:01 | はてなブックマーク - SRM552 Div1 900 - cafelier@SRM

問題文を整理すると、

  • 「upTo (≦10^10) 以下の自然数で、次の条件を満たすものの個数は?」
  • 条件:素因数分解 p1^k1 p2^k2 ... pm^km したとき
    • pi ≦ maxmalPrime (≦10^6)
    • ki は奇数

が問われている。計算量が分析できてないので考える。

class HolyNumbers { public:
   long long count(long long upTo, int maximalPrime)
   {
      return rec(eratosthenes(maximalPrime), 0, upTo);
   }

   static vector<LL> eratosthenes(int N)
   {
      vector<LL> ps;
      vector<bool> is_prime(N+1, true);
      for(int p=2; p<=N; ++p)
         if(is_prime[p]) {
            ps.push_back(p);
            for(int q=p+p; q<=N; q+=p)
               is_prime[q] = false;
         }
      return ps;
   }

   static LL rec(const vector<LL>& ps, int i, LL upto)
   {
      if( i==ps.size() || upto<ps[i] )
         return 1;

      // 以下2行が枝刈り
      // ps[i]の2乗より小さかったら高々1回しか割れないのでパターン数は数えればわかる
      if( upto < ps[i]*ps[i] )
         return upper_bound(ps.begin()+i, ps.end(), upto)-ps.begin() - i + 1;

      LL sum = rec(ps, i+1, upto);
      for(LL p=ps[i], pk=p; pk<=upto; pk*=p*p)
         sum += rec(ps, i+1, upto/pk);
      return sum;
   }
};

ほぼナイーブな全探索。

  • upTo を 2, 8, 32, 128, 512, ... で割ってみる
  • その結果を 3, 27, 243, ... で割ってみる
  • その結果を 5, 125, ... で

を再帰で、エラトステネスの篩で求めた素数リストに対してひたすら繰り返し。特にメモ化もしない。

【性質1】途中の2行の枝刈りをしなかった場合、計算時間 = O(recの呼び出し回数) = O(答え)

  • 理由: if(upto<ps[i]) return 1; が入っているので、再帰本体のfor文に到達したときに1回は必ず回る。トーナメント形式の対戦回数がO(チーム数)であるのと同じ理屈で、再帰の時は必ず分岐する再帰の呼び出し回数はO(leafの数)。この場合は再帰のleafでreturn 1してその数を数えて答えているので、これは答えの値に等しい。

以下 upTo は最大値 10^10 固定で考える。上の議論により計算時間は O(upTo) で抑えられたけど、これでは大きすぎる。maximalPrime=200 で答えが1000万くらい。ここらへんまでが特に枝刈りしなくても行ける範囲。

10^7オーダに落とすには、maximalPrime=10^6のケースで1000倍高速化すればよい。枝刈りによってどのくらい速くなるかというと、

if( upto < ps[i]*ps[i] )
   return upper_bound(ps.begin()+i, ps.end(), upto)-ps.begin() - i + 1;

要はまとめて数えることでleafがどれだけ減ったかと考えると、このreturn文が平均でいくつを返すかによって決まる。平均で1000を返すなら1000倍速い(たぶん)。

1000以上を返すのはどういう場合かというと

pの1000個先の素数 <= upto < 素数p^2

の時で、枝刈れるならすぐ刈ってるので割と upto ≒ 素数p^2 っぽいと仮定すると

pの1000個先の素数 < 素数p^2

なら十分で、これは調べてみると p=101 辺りから成り立つようなので、まあだいたいほとんどの素数で成り立っていると言える、のかな?すごく嘘っぽいですね。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20120818
 | 

presented by cafelier/k.inaba under CC0