SRM643 div1 easy TheKingsFactorization

考えたこと

• 素因数分解は試し割りでO(sqrt(N))なので愚直にやるのは間に合わない
• ヒントとして与えられた素因数でNを割っておいていい
• primes[i] = primes[i+1] ならば間に入る素因数はprime[i]で確定
• O(primes[i+1]-primes[i])かけて全て試せば間に入る素因数を特定できる
• 間が広すぎるとき間に合わない
• 間が10⁶以上のときprimes[i+1] >= 10^6になるのでN <= 10^12 くらいで抑えられる
• 間が広いときはO(sqrt(N))で狭いときはO(primes[i+1]-primes[i])で間の数を特定すればよい

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class TheKingsFactorization {
   public:
   vector<long long> getVector(long long N, vector<long long> primes)
  {
    int n = primes.size();
    vector<ll> v;

    REP(i, n) {
      v.PB(primes[i]);
      N /= primes[i];
    }

    // nはせいぜい30~40くらい？
    REP(i, n-1) {
      if(primes[i] == primes[i+1]) {
        v.PB(primes[i]);
        N /= primes[i];
      } else if(primes[i+1] - primes[i] <= 1e6){
        FOR(j, primes[i], primes[i+1]+1) {
          if(N%j == 0) {
            v.PB(j);
            N /= j;
            break;
          }
        }
      } else {
        for(int j=primes[i]; j<=primes[i+1] && j*j <= N; ++j) {
          if(N%j == 0) {
            v.PB(j);
            N /= j;
            break;
          }
        }
      }
    }

    if(N!=1) {
      v.PB(N);
      N = 1;
    }

    sort(ALL(v));
    return v;
  }
};