The 2021 ICPC Asia Regionals Online Contest (II) L Euler Function

可能是這天 真的狀态太差了 寫了一半居然懷疑複雜度 沒寫了。。。

我們對于每一個因子分開去維護

對于一個數x = p1c1p2c2p3C3…

每一個因子的歐拉函數為

p1c1 (p1-1)/p1

如果第一次修改目前因子

那麼乘上p1c1(p-1)/p

如果有了直接乘上p1^c1

歐拉函數是奇性函數如果p q互質那麼pq的歐拉函數就是p的歐拉函數*q的歐拉函數

想清楚發現 對于每個點最多單點修改25次

明明在比賽中敲了一半多了 自己把他放棄

貼一下ac代碼給大家看看

100以内一共25個質數

然後用二進制表示每一位有沒有存在

如果向下修改的那個狀态和這段區間有差别 那麼直接暴力修改這一段

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6+10,mod=998244353;
typedef long long LL;
int a[N],st[N];
int t[N];
struct Node{
	int l,r;
	LL tag,sum,val,cnt;
	void change(LL k1){
		tag*=k1;
		tag%=mod;
		sum=k1%mod*sum%mod;
	}
	
}tr[N<<2];
int p[N],cnt;
LL qpow(LL x,LL k){
	LL res=1;
	while(k){
		if(k&1)res=res*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return res;
}
void push_up(int u){
	tr[u].cnt=(tr[u<<1].cnt&tr[u<<1|1].cnt);
	tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%mod;
}
void build(int u,int l,int r){
	tr[u]={l,r,1,1,1,1};
	if(l==r){
		tr[u].sum=a[l];
		for(int i=1;i<=cnt;i++){
			if(a[l]%p[i]==0){
				tr[u].cnt|=1<<i;
				tr[u].sum*=t[i];
				tr[u].sum%=mod;
			}
		}
		return ;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	push_up(u);
}
void push_down(int u){
	if(tr[u].tag!=1){
		tr[u<<1].change(tr[u].tag);
		tr[u<<1|1].change(tr[u].tag);
		tr[u].tag=1;
	}
}
void change(int u,int l,int r,LL k1,LL k2){
	if(tr[u].l>r||tr[u].r<l)return ;
	if(l<=tr[u].l&&tr[u].r<=r&&((tr[u].cnt&k2)==k2)){
		tr[u].change(k1);
		return ;
	}
	if(tr[u].l==tr[u].r){
		tr[u].sum*=k1;
		tr[u].sum%=mod;
		for(int i=1;i<=cnt;i++){
			if((k2>>i&1)&&(!(tr[u].cnt>>i&1))){
				tr[u].sum*=t[i];
				tr[u].sum%=mod;
				tr[u].cnt|=1<<i;
			}
		}
		return ;
	}
	push_down(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid)change(u<<1,l,r,k1,k2);
	if(r>mid)change(u<<1|1,l,r,k1,k2);
	push_up(u);
}
LL query(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r){
		return tr[u].sum;
	}
	push_down(u);
	int mid=tr[u].l+tr[u].r>>1;
	long long sum=0;
	if(l<=mid)sum+=query(u<<1,l,r);
	if(r>mid)sum+=query(u<<1|1,l,r);
	sum%=mod;
	push_up(u);
	return sum;
}
int main(){
	for(int i=2;i<=100;i++){
		if(!st[i]){
			p[++cnt]=i;	
			t[cnt]=(i-1)*qpow(i,mod-2)%mod;
		}
		for(int j=i;j<=100;j+=i){
			st[j]=1;
		}
	}
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,l,r,x;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			printf("%lld\n",query(1,l,r));
		}else{
			scanf("%d",&x);
			LL tt=0;
			for(int j=1;j<=cnt;j++){
				if(x%p[j]==0){
					tt|=1<<j;
				}
			}
			change(1,l,r,x,tt);
		}
	}
	return 0;
}