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(素因数xkの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; }