SRM 661 div1 easy MissingLCM

問題

問題概要

lmc(1..M)=lcm(N+1,M)となる最小のMを求める.

解法

まず,
1,..,N,N+1,…,M
N+1,…,M
のlcmが一致することから,1…Nの中にlcmを作るのに寄与したものがいないので, 1…Nのなかに含まれる最大の素数の2倍の数がすくなくともMまでに含まれていなければならない. さらにM=2Nのとき, 1,..Nの数の倍数はすべて1,..Mの中に含まれるので, 必ず1,..Nがlcmに寄与しなくなるので, Mは最大でも2Nということになる. よってMの範囲は[(N以下で最大の素数), 2N]となる.
あとは,Mをその範囲で動かしながらlcm(1..M)とlcm(N+1,M)を高速に求めていけばよい.
範囲 lcmを求める計算量だが, 前処理を無視して範囲を[l,r]とすると, (r-l)logNとなり, おおよそO(N*logN)という結果になる. Mをインクリメントしていくが, その度に[l,r]のlcm(l,..r)を計算し直すとTLEしてしまう. なので、右端を1つ追加する感じでうまく処理する.

ミス

素因数分解を高速にやる方法がわからなかった. prime[i] := iが素数の場合には0, 以外のときはiを割りる最大の素数 となる配列を前処理で作っておくことで, 1つの数のlcm(素因数x^kのk)を求めるのがlognでできるようになる.

コード

AC

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

class primelib{
public:
    vector<int> prime; //prime[i] := iが素数の場合には0, 以外のときはiを割りる最大の素数
    vector<int> memo; 
    primelib(int size):prime(size + 10, 0), memo(size + 10, 0){
        prime_factorization(size + 1);
    }
    //[left,right]までのlcmがmemo[x]:=xの次数 として表される
    void getlcm(int left, int right){
        // fill(memo.begin(), memo.end(), 0); //0で初期化
        for (int i = max(2, left); i <= right; ++i){
            map<int, int> degree; //<x, k> := x^k
            int tmp = i;
            while(prime[tmp]){
                degree[prime[tmp]]++;
                tmp /= prime[tmp]; //最大の素数で割る
            }
            degree[tmp]++; //残った素数をカウント
            //memo[x] := [left, right]までを素因数分解した最大のxの次数を更新
            for(auto u : degree){
                memo[u.first] = max(memo[u.first], u.second);
            }
        }
    }
private:
    //prime[i] := iが素数の場合には0, 以外のときはiを割りる最大の素数
    //これを使えばO(logn)で素因数分解可能
    void prime_factorization(int n){
        for (int i = 2; i <= n; i++) {
            if (prime[i] == 0) {
                for (int j = 2; j * i <= n; j++) {
                    prime[i * j] = i;
                }
            }
        }
    }
};

class MissingLCM
{
public:
    int getMin(int N){
        int ans;
        primelib pba(2 * N), pbb(2 * N);
        for (int i = N; i >= 1; --i){
            if(pba.prime[i] == 0){
                ans = i; break;
            }
        }
        //答えが[2 * ans, 2*N]の中
        pba.getlcm(N + 1, 2 * ans); pbb.getlcm(1, 2 * ans);
        int ret;
        for (int i = 2 * ans; i <= 2 * N; ++i){
            if(pba.memo == pbb.memo){//lcmが一致しているか
                ret = i;
                break;
            }
            //i+1を付け足す
            pba.getlcm(i + 1, i + 1); pbb.getlcm(i + 1, i + 1);
        }
        return ret;
    }
};

int main(void){
    MissingLCM lc;
    auto ret = lc.getMin(279841);
    printf("%d\n", ret);//559682
    return 0;
}

TLE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;


class primelib{
public:
    vector<int> prime; //prime[i] := iが素数の場合には0, 以外のときはiを割りる最大の素数
    vector<int> memo; 
    primelib(int size):prime(size + 10, 0), memo(size + 10, 0){
        prime_factorization(size + 1);
    }
    //[left,right]までのlcmがmemo[x]:=xの次数 として表される
    void getlcm(int left, int right){
        fill(memo.begin(), memo.end(), 0); //0で初期化
        for (int i = max(2, left); i <= right; ++i){
            map<int, int> degree; //<x, k> := x^k
            int tmp = i;
            while(prime[tmp]){
                degree[prime[tmp]]++;
                tmp /= prime[tmp]; //最大の素数で割る
            }
            degree[tmp]++; //残った素数をカウント
            //memo[x] := [left, right]までを素因数分解した最大のxの次数を更新
            for(auto u : degree){
                memo[u.first] = max(memo[u.first], u.second);
            }
        }
    }
private:
    //prime[i] := iが素数の場合には0, 以外のときはiを割りる最大の素数
    //これを使えばO(logn)で素因数分解可能
    void prime_factorization(int n){
        for (int i = 2; i <= n; i++) {
            if (prime[i] == 0) {
                for (int j = 2; j * i <= n; j++) {
                    prime[i * j] = i;
                }
            }
        }
    }
};

class MissingLCM
{
public:
    int getMin(int N){
        int ans;
        primelib pba(2 * N), pbb(2 * N);
        for (int i = N; i >= 1; --i){
            if(pba.prime[i] == 0){
                ans = i; break;
            }
        }
        printf("%d\n", ans * 2);
        //答えが[2 * ans, 2*N]の中
        int ret;
        for (int i = 2 * ans; i <= 2 * N; ++i){
            pba.getlcm(N + 1, i); pbb.getlcm(1, i);
            if(pba.memo == pbb.memo){//lcmが一致しているか
                ret = i;
                break;
            }
        }
        return ret;
    }
};

/* TLE */
int main(void){
    MissingLCM lc;
    auto ret = lc.getMin(279841);
    printf("%d\n", ret);//559682
    return 0;
}