【TIOJ 1872】最小公倍數

原題連結：http://tioj.infor.org/problems/1872
這題本來沒什麼想法，看題解想了好久才搞懂QQ

首先我們要先對詢問區間的右界排序(QlgQ)
然後利用差分的概念，維護序列b[i]=query(i,r)/query(i+1,r)
也就是計算詢問往左擴大一個後會需要多乘多少
這裡我是用bit維護，這樣對於一個詢問[l,r]，固定r後求得的答案就是bit_query(r)*inv(bit_query(l-1))
維護良好的話，詢問複雜度會是QlgN

再來是維護的部分
當我們要增加一個r的時候，我們對於每個a[r]的質因數p做分開處理(質因數分解O(NlgN))
假想r-1以前的維護都已經完成，那麼對於一個質數p，我們將會維護出一個從a[1]~a[r-1]的「嚴格遞減單調隊列」
其中內含的是a[i]中最大的p冪次因數

這時候就可以開始用一個stack做單調隊列的維護，先求出a[r]中最大的p冪次因數，冪次為c
則當top的冪次r：
r<=c 該top原位置的b[i]必須被更動(因為表示這個冪次r會完全被c蓋住)，然後就可以把top拔掉了
r>c 該top原位置的b[i]必須稍做更動(增加幅度減少)，並把c推入stack後更新b[r]退出(更後面的元素我們可以相信他們已經被前面的元素更新完了)

更新b[r]、更動b[i]的部分分別一個是用乘的，一個是用除的(乘反元素)
這裡我在線篩的時候有預處理把每個質數的冪次和反元素都蓋好(複雜度NlgN)，所以更新更動都是lgN
對於每個質數，每個元素至多加入一次、拔掉一次，均攤O(1)，單一質數最慘複雜度O(NlgN)

但注意到數字最大只有10^6，所以要卡最緊也只能多約lgC個質數(實際上是更好的一個反函數)，維護總複雜度O(NlgClgN)

總複雜度O(Q(lgQ+lgN)+NlgClgN)

附上code:

	#pragma GCC optimize("Ofast")
	#include <bits/stdc++.h>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define ll long long
	#define pb push_back
	#define MEM(i,j) memset(i,j,sizeof i)
	#define F first
	#define S second
	#define ET cout << "\n"
	#define DB(a,s,e) {for(int i=s;i<e;i++) cout << a[i] << " ";ET;}
	using namespace std;
	struct Query
	{
	ll L,R,place;
	bool operator<(const Query &a)const{
	return R<a.R;
	}
	}query[1000001];
	const ll MOD=1e9+7;
	ll min_prime[1000001],num[1000001],bit[1000001],n,ans[1000001];
	vector<ll> prime,po[1000001],invpo[1000001];
	vector<pair<ll,ll> > st[1000001];
	ll pow(ll a,ll b)
	{
	ll re=1;
	for(;b;b/=2,a=a*a%MOD)
	if(b&1) re=re*a%MOD;
	return re;
	}
	void build_prime()
	{
	min_prime[1]=1;
	int i,j;
	for(i=2;i<=1000000;i++)
	{
	if(!min_prime[i])
	{
	prime.pb(i);
	for(j=1,po[i].pb(1),invpo[i].pb(1);i*po[i][j-1]<=1000000;j++)
	po[i].pb(i*po[i][j-1]),invpo[i].pb(pow(po[i][j],MOD-2));
	}
	for(ll x:prime)
	{
	if(i*x>1000000) break;
	min_prime[i*x]=x;
	if(i%x==0) break;
	}
	}
	}
	ll lowbit(ll x)
	{
	return x&-x;
	}
	void modify(ll x,ll v)
	{
	for(ll tmp=x;tmp<=n;tmp+=lowbit(tmp)) bit[tmp]=bit[tmp]*v%MOD;
	}
	ll bit_query(ll x)
	{
	ll re=1;
	for(ll tmp=x;tmp;tmp-=lowbit(tmp)) re=re*bit[tmp]%MOD;
	return re;
	}
	ll add(ll R)
	{
	ll tmp=num[R],x,c,w;
	while(min_prime[tmp]>1)
	{
	x=min_prime[tmp];
	for(c=0;tmp%x==0;tmp/=x) c++;
	w=0;
	while(!st[x].empty())
	{
	if(st[x].back().F>c)
	{
	if(w!=c)
	modify(st[x].back().S,invpo[x][c-w]);
	break;
	}
	else
	modify(st[x].back().S,invpo[x][st[x].back().F-w]),w=st[x].back().F,st[x].pop_back();
	}
	st[x].push_back({c,R}),modify(R,po[x][c]);
	}
	if(tmp>1)
	{
	x=tmp,c=1,w=0;
	while(!st[x].empty())
	{
	if(st[x].back().F>c)
	{
	if(w!=c)
	modify(st[x].back().S,invpo[x][c-w]);
	break;
	}
	else
	modify(st[x].back().S,invpo[x][st[x].back().F-w]),w=st[x].back().F,st[x].pop_back();
	}
	st[x].push_back({c,R}),modify(R,po[x][c]);
	}
	}
	int main()
	{jizz
	ll q,i,now=0;
	build_prime();
	cin >> n >> q;
	for(i=1;i<=n;++i)
	cin >> num[i],bit[i]=1;
	for(i=0;i<q;++i)
	cin >> query[i].L >> query[i].R,query[i].place=i;
	sort(query,query+q);
	for(i=0;i<q;)
	{
	while(now<query[i].R) add(++now);
	while(i<q && query[i].R==now)
	if(query[i].L==query[i].R) ans[query[i].place]=num[query[i].L],++i;
	else ans[query[i].place]=bit_query(query[i].R)*pow(bit_query(query[i].L-1),MOD-2)%MOD,++i;
	}
	for(i=0;i<q;i++)
	cout << ans[i] << "\n";
	}

view raw gistfile1.txt hosted with ❤ by GitHub