cafelier@SRM

SRM552 Div1 900

SRM | 23:01 |

問題文を整理すると、

• 「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;

      // 以下２行が枝刈り
      // ps[i]の2乗より小さかったら高々１回しか割れないのでパターン数は数えればわかる
      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, ... で

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

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

• 理由： if(upto<ps[i]) return 1; が入っているので、再帰本体のfor文に到達したときに１回は必ず回る。トーナメント形式の対戦回数が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 辺りから成り立つようなので、まあだいたいほとんどの素数で成り立っていると言える、のかな？すごく嘘っぽいですね。