cafelier@SRM

TCO10 R3 250

あとで | 11:56 |

• 普通に素因数分解的なことして十分間に合うじゃないですかー

class SieveOfEratosthenes { public:
   vector<int> eratos(int M)
   {
      vector<bool> isComposite(M+1);
      vector<int> ps;
      for(int p=2; p<=M; ++p)
         if( !isComposite[p] )
         {
            ps.push_back(p);
            for(LL q=LL(p)*p; q<=M; q+=p)
               isComposite[q] = true;
         }
      return ps;
   }

   int minFactor(int N, const vector<int>& ps)
   {
      for(int i=0; i<ps.size(); ++i)
         if( N % ps[i] == 0 )
            return ps[i];
      return INT_MAX;
   }

   int lastScratch(int maxNum)
   {
      vector<int> ps = eratos(int(sqrt(double(maxNum))));
      int P = ps.back();
      int M = P*P;
      for(int Q=P+1; P*Q<=maxNum; ++Q)
         if( minFactor(Q,ps) >= P )
            M = P*Q;
      return M;
   }
};

• Pから2Pの間には別の素数があるので
  • Q はたかだか4Pまで考えればよくて
  • minFactorは…大きい素数の掛け算でできてる値の時しか時間かからないので、まあ大丈夫なのか
• Pがせいぜい5万弱で
  • Pまでの素数は5000個とかで
  • なので最悪でも3*5万*5000だし、明らかにほとんどの場合5000もかからないし
    • 1/2 は 1イテレーションで終わる
    • (1-1/2)*1/3=1/6 は 2イテレーションで終わる
    • (1-1/2-1/6)*1/5=1/15 は 3イテレーションで終わる
    • (1-...-1/15)*1/7=4/105 は 4
    • 残り 8/35
    • 思いっきり大目に見て残り平均2000回かかるとしても 1/2 + 2/6 + 3/15 + 16/105 + 8/35 2000≒500とかだし実際はもっと少ないだろう
  • これは十分間に合うなあ
  • なんで本番で見積もれなかったんだろう…

• 8以外の場合は2個でいいのは
  • p*q*r (p<q<r) は q*q より前に消される</li>
  • p*q*q (p<q) は q*q より前に消される</li>
  • p*p*q (p<q) は、pの次の素数 < p*p, q なので (pの次の素数)*(pの次の素数) より早く消される</li>
  • p*p*p は… (pの次の素数)*(pの次の素数) と、2**3 vs 3**2 のところだけ逆転している！
• こうか。ふむふむ