Codeforces #864 : Div2 E. Li Hua and Array

これは面倒だけど考察は難しくないな。
https://codeforces.com/contest/1797/problem/E

問題

整数列Aが与えられる。
以下のクエリに答えよ。

• 区間[L,R]が指定される。区間内の各要素A[x]を、φ(A[x])で置き換える。
• 区間[L,R]が指定される。区間内の各要素A[x]を1つ選び、φ(A[x])で置き換えることを繰り返して全要素同じ値にするには何回処理が必要か。

解法

トーシェント関数を繰り返し適用すると、割と早い段階で1になる。
そこで、前者のクエリに対してはA[x]!=1となる要素のindexだけsetで管理すればよい。
後者については、SegTreeに区間の値を等しくする際の、最終的な値と要素数と処理回数を載せればよい。

int N,M;
int T[5150505];

int A[101010];
template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		if(l[0]==0) return r;
		if(r[0]==0) return l;
		int step=l[1]+r[1];
		while(l[0]!=r[0]) {
			if(l[0]>r[0]) {
				step+=l[2];
				l[0]=T[l[0]];
			}
			else {
				step+=r[2];
				r[0]=T[r[0]];
			}
		}
		return {l[0],step,l[2]+r[2]};
	};
	
	SegTree_1(){val=vector<V>(NV*2);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return {0,0,0};
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, int v) {
		entry += NV;
		val[entry]={v,0,1};
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<array<int,3>,1<<20> st;
set<int> S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=5050505;i++) T[i]=i;
	for(i=2;i<=5000500;i++) {
		if(T[i]==i) {
			for(j=i;j<=5000000;j+=i) T[j]=T[j]/i*(i-1);
		}
	}
	
	cin>>N>>M;
	S.insert(N);
	FOR(i,N) {
		cin>>A[i];
		if(A[i]>1) S.insert(i);
		st.update(i,A[i]);
	}
	while(M--) {
		int L,R;
		cin>>i>>L>>R;
		L--;
		if(i==1) {
			int cur=L;
			while(1) {
				auto it=S.lower_bound(cur);
				cur=*it;
				if(cur>=R) break;
				A[cur]=T[A[cur]];
				if(A[cur]==1) S.erase(cur);
				st.update(cur,A[cur]);
				cur++;
			}
		}
		else {
			auto a=st.getval(L,R);
			cout<<a[1]<<endl;
			
		}
	}
	
	
}

まとめ

トーシェント関数の適用を繰り返すと急激に値が小さくなることを知ってれば、後は単純。