Topcoder SRM599 Div1Easy BigFatInteger

topcoder

問題

Kという数に以下の2通りの操作をして、Kを大きくしていきます。（最初はK=1）です。

・Kに素数をかける。
・KにKの約数のいずれかをかける。

２数A,Bが与えられたとき、KをA^Bにするのに最小の操作回数を求めなさい。

制約

A,B<=10^6


解法

Aを素因数分解して、各素因数の指数をB倍すればA^Bの素因数分解になります。

まず出てくる素因数全てをかけます。この操作は省けませんね。
次に、一度出てきた素因数は倍々ゲームで増やすことができます。

2 → 2^2(2をかける) → 2^4(4をかける) → 2^8(16をかける)
という具合です。このことから2^n＜x＜2^(n+1)なるxについて、
aからa^xを作るために必要な操作回数はn+1回であることがわかります。

そして、この操作は各素因数に対して同時に行えます。よって、素因数の指数部が最大のものが最終的な操作回数を決めるということになります。


プログラム

#include<iostream> 
#include <fstream> 
#include <stdio.h> 
#include <stdlib.h> 
#define _USE_MATH_DEFINES 
#include <math.h> 
#include<string> 
#include<vector> 
#include<cmath> 
#include<stack> 
#include<queue> 
#include<sstream> 
#include<algorithm> 
#include<map> 
#include<complex> 
#include<ctime> 
#include<set> 
using namespace std; 


#define li      long long int 
#define rep(i,to)  for(li i=0;i<((li)(to));i++) 
#define pb      push_back 
#define sz(v)    ((li)(v).size()) 
    li sosu[1001000]={0}; 

class BigFatInteger { 

  public: 

  int minOperations(int A, int B) { 
    rep(i,1001000)sosu[i]=1; 
    sosu[0]=sosu[1]=0; 
    for(li i=2;i<1001000/2; i++){ 
      if(sosu[i]) 
      for(li j=2; i*j<1001000-1; j++){ 
        sosu[i*j]=0; 
      } 
    } 

    vector<li> sosus; 
    rep(i,1001000)if(sosu[i])sosus.pb(i); 

    vector<li> yks; 
    rep(i,sz(sosus)){ 
      if(A%sosus[i]==0){ 
        yks.pb(0); 
        while(A%sosus[i]==0){ 
          yks[sz(yks)-1]++; 
          A/=sosus[i]; 
        } 
      } 
    } 
    li res=0; 
    li ma=0; 
    rep(i,sz(yks)){ 
      ma=max(ma, yks[i]); 
    } 
    ma*=B; 
    res+=sz(yks); 
    li ni=1; 
    while(ma>ni){ 
      ni<<=1; 
      res++; 
    } 
    return res; 
  } 
};

雑感
素因数分解を書くのと正しそうなのを確認するのに時間が多少かかったために得点が低くなってしまったので、
典型アルゴリズムはライブラリ持っておこうという思いを一層強くしたのでありました。