kmjp's blog

競技プログラミング参加記です

第3回 ドワンゴからの挑戦状 本選 : B - ニワンゴくんの約数

また力技で解く…。
http://dwacon2017-honsen.contest.atcoder.jp/tasks/dwango2017final_b

問題

N要素の数列X[i]が与えられる。
Q個のクエリ(L,R)が与えられるので、X[L..R]の積の約数の個数を求めよ。

解法

約数の個数は、各素因数の指数に1を加えたものの積である。
X[L...R]の区間を1要素増減させる場合、その分の素因数の指数の変化分だけ考慮すれば、増減後の約数の位置が求められる。
よって、区間の大きさを少し変えるコストが小さいため、Mo's algorithmで解くことができる。

なお、区間の増減の際複数の素因数に対し処理を行う必要があるので、Mo's algorithmを適用するだけだとまだちょっと重くTLEする。
Editorialでは、小さな素因数に対しては区間に対する素因数の指数の総和を前処理することで高速化している。
以下のコードではこのアプローチを取らず、同一の指数の複数回加減算をまとめたり、インラインアセンブラによる除算の高速化で無理やり通している。

int N,Q;
ll mo=1000000007;
int X[101010];
vector<pair<int,int>> E[101010];
int num[101010];
int rev[2010100];
int last[101010];
int L[101010],R[101010];
ll ret[101010];
const int DIV=400;
vector<pair<int,int>> ev[404];
int cur;

int id;
vector<int> up;

vector<pair<int,int>> enumpr(ll n) {
	map<int,int> M;
	for(int i=2;i*i<=n;i++) while(n%i==0) M[i]++,n/=i;
	if(n>1) M[n]++;
	vector<pair<int,int>> V;
	FORR(r,M) V.push_back({r.first,r.second});
	return V;
}

inline int mulmod(int a,int b,int mo) {
	int d,r;
	if(a==0 || b==0) return 0;
	if(a==1 || b==1) return max(a,b);
	__asm__("mull %4;"
	        "divl %2"
		: "=d" (r), "=a" (d)
		: "r" (mo), "a" (a), "d" (b));
	return r;
}

void add(int x) {
	FORR(r,E[X[x]]) {
		if(last[r.first]!=id) {
			cur=mulmod(cur,rev[num[r.first]],mo);
			last[r.first]=id;
			up.push_back(r.first);
		}
		num[r.first] += r.second;
	}
}
void del(int x) {
	FORR(r,E[X[x]]) {
		if(last[r.first]!=id) {
			cur=mulmod(cur,rev[num[r.first]],mo);
			last[r.first]=id;
			up.push_back(r.first);
		}
		num[r.first] -= r.second;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=100000;i++) {
		E[i]=enumpr(i);
		num[i]=1;
	}
	rev[1]=1;
	for(i=2;i<=2000000;i++) rev[i] = 1LL*rev[mo % i] * (mo - mo / i) % mo;
	
	cin>>N>>Q;
	FOR(i,N) cin>>X[i];
	
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		L[i]--,R[i]--;
		ev[L[i]/DIV].push_back({R[i],i});
	}
	
	MINUS(last);
	
	int LL=0,RR=-1;
	cur=1;
	FOR(i,304) if(ev[i].size()) {
		sort(ALL(ev[i]));
		FORR(r,ev[i]) {
			x = r.second;
			id=x;
			up.clear();
			
			while(L[x]<LL) add(--LL);
			while(RR<=R[x]) add(RR++);
			while(LL<L[x]) del(LL++);
			while(R[x]+1<RR) del(--RR);
			FORR(t,up) {
				cur=mulmod(cur,num[t],mo);
			}
			ret[x]=cur;
		}
	}
	FOR(i,Q) cout<<ret[i]<<endl;
	
	
}

まとめ

いかにも過去ありそうな問題だけどまだなかったのかね。

広告を非表示にする