[TIOJ] 1338. 因數元素

題目連結:http://tioj.infor.org/problems/1338

---

先小抱怨個，我因為通常都比較節省記憶體(?所以原本sparse table用vector array，結果卻因為push_back而被一直卡到時限(這題有夠緊的阿QAQ)，還有我不小心算錯範圍...。
正題:首先很明顯的可以知道若$gcd(C_{[L,R)})=C_k$（$L\leq k< R$），則$C_{[L,R)}$有因數元素。此外若$C_{[L,R)}$有因素元素，則其必定為$min(C_{[L,R)})$。合併兩個條件後，就發現本題可以轉化為類RMQ問題，開個sparse table存gcd跟min，那我們就可以$O(1)$做到query。

#include <algorithm>
#include "lib1338.h"
typedef long long lld;

using std::min;
using std::__gcd;


lld minSTable[21][1000005];
lld gcdSTable[21][1000005];


void init(int N, lld arr[]){
	int obov=0;
	for(int i=0;i<N;i++,obov++){
		minSTable[0][obov]=arr[i];
		gcdSTable[0][obov]=arr[i];
	}
	for(int i=1;(1<<i)-1<N;i++){
		obov=0;
		for(int j=0;(1<<i)+j-1<N;j++,obov++){
			lld mA = minSTable[i-1][j];
			lld mB = minSTable[i-1][j+(1<<(i-1))];
			lld gA = gcdSTable[i-1][j];
			lld gB = gcdSTable[i-1][j+(1<<(i-1))];
			minSTable[i][obov]=min(mA,mB);
			gcdSTable[i][obov]=__gcd(gA,gB);
		}
	}
}

int query(int L, int R){
	int k = 31-__builtin_clz(R-L);
	lld m = min(minSTable[k][L], minSTable[k][R-(1<<k)]);
	lld g = __gcd(gcdSTable[k][L], gcdSTable[k][R-(1<<k)]);
	return m==g;
}