The 2021 ICPC Asia Regionals Online Contest (II)，PTA
#include <bits/stdc++.h>
//#define endl '
'
#define lose {printf("NO
");return;}
#define win {printf("YES
");return;}
#define all(A) (A).begin(),(A).end()
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define PER(I, A, B) for (int I = (A); I >= (B); --I)
#define DB(A) cout<<(A)<<endl
#define lson k*2
#define rson k*2+1
#define fi first
#define se second
#define PB push_back
#define Pair pair<int,int>
#define MP make_pair
#define ll long long
#define ull unsigned long long
//#define int ll
using namespace std;
#define DB1(args...) do { cout << #args << " : "; dbg(args); } while (0)
void dbg() { std::cout << " #
"; }
template<typename T, typename...Args>
void dbg(T a, Args...args) { std::cout << a << ' '; dbg(args...); }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
template <typename T> void print(T x) {
if (x < 0) { putchar('-'); print(x); return ; }
if (x >= 10) print(x / 10);
putchar((x % 10) + '0');
}
template <typename T> void println(T x) {
print(x);
putchar('
');
}
//var
const int maxn=1e5+10;
const int MAX=1000;
const int inf=0x3f3f3f3f;
const int mod=998244353;
//head
int n,m;
int c[maxn];
int cnt[maxn][30];
struct readtype
{
bitset<30> op;
int val;
} a[maxn];
/**********************************************************/
int pri[110];
int pvis[110];
int pnum=-1;
void getprime()
{
FOR(i,2,100)
{
if (!pvis[i])
{
pri[++pnum]=i;
int j=i+i;
while (j<=100)
{
pvis[j]=1;
j+=i;
}
}
}
assert(pnum==24);
}
int phi(int n)//计算欧拉函数
{
int ans = n;
for(int i = 2; i * i <= n; ++i)
{
if(n % i == 0)
{
ans = ans / i * (i - 1);
while(n % i == 0) n /= i;
}
}
if(n > 1) ans = ans / n * (n - 1);
return ans;
}
void init()
{
getprime();
FOR(i,1,100000)
{
int now=i;
FOR(j,0,24)
{
while (now%pri[j]==0)
{
cnt[i][j]++;
now/=pri[j];
}
}
}
assert(cnt[16][0]==4);
assert(cnt[18][0]==1);
assert(cnt[18][1]==2);
FOR(i,1,n)
{
a[i].op.reset();
a[i].val=phi(c[i]);
FOR(j,0,24) if (cnt[c[i]][j]) a[i].op.set(j);
}
}
int add(int a,int b)
{
int c=a+b;
if (c>=mod) c-=mod;
return c;
}
int mul(int a,int b)
{
ll c=1ll*a*b%mod;
return (int)c;
}
int fpow(int x,int k)
{
int ans=1;
while (k)
{
if (k&1) ans=mul(ans,x);
k>>=1;
x=mul(x,x);
}
return ans;
}
struct tree
{
int l,r;
bitset<30>op;
int w;
int z;
} t[maxn*4];
void pushup(int k)
{
t[k].op=t[lson].op&t[rson].op;
t[k].z=add(t[lson].z,t[rson].z);
}
void pushdown(int k)
{
int w=t[k].w;
if (w==1) return;
t[lson].w=mul(t[lson].w,w);
t[rson].w=mul(t[rson].w,w);
t[lson].z=mul(t[lson].z,w);
t[rson].z=mul(t[rson].z,w);
t[k].w=1;
}
void build(int k,int l,int r)
{
t[k].l=l,t[k].r=r,t[k].w=1;
if (l==r)
{
t[k].op=a[l].op;
t[k].z=a[l].val;
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(k);
}
void update(int k,int l,int r,int p,int num)
{
// DB1(k,t[k].l,t[k].r,l,r);
if (t[k].l==l&&t[k].r==r&&t[k].op[p])
{
int tmp=fpow(pri[p],num);
t[k].w=mul(t[k].w,tmp);
t[k].z=mul(t[k].z,tmp);
return;
}
if (t[k].l==t[k].r)
{
t[k].z=mul(t[k].z,pri[p]-1);
int tmp=fpow(pri[p],num-1);
t[k].z=mul(t[k].z,tmp);
t[k].op[p]=1;
return;
}
pushdown(k);
int mid=(t[k].l+t[k].r)>>1;
if (r<=mid) update(lson,l,r,p,num);
else if (l>mid) update(rson,l,r,p,num);
else
{
update(lson,l,mid,p,num);
update(rson,mid+1,r,p,num);
}
pushup(k);
}
int query(int k,int l,int r)
{
// DB1(k,t[k].l,t[k].r,l,r);
if (t[k].l==l&&t[k].r==r)
{
return t[k].z;
}
pushdown(k);
int mid=(t[k].l+t[k].r)>>1;
if (r<=mid) return query(lson,l,r);
else if (l>mid) return query(rson,l,r);
else
{
int tmp1=query(lson,l,mid);
int tmp2=query(rson,mid+1,r);
return add(tmp1,tmp2);
}
}
void solve()
{
read(n);read(m);
FOR(i,1,n)
{
read(c[i]);
}
init();
build(1,1,n);
vector<int>ans;
// FOR(i,1,n) DB1(i,a[i].val);
FOR(i,1,m)
{
int op;
scanf("%d",&op);
if (op==0)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
FOR(j,0,24) if (cnt[w][j])
{
update(1,x,y,j,cnt[w][j]);
}
}
else
{
int l,r;
scanf("%d%d",&l,&r);
ans.PB(query(1,l,r));
}
}
int anslen=ans.size();
FOR(i,0,anslen-1)
{
printf("%d",ans[i]);
if (i!=anslen-1) printf("
");
}
}
signed main()
{
// freopen("read.txt", "r", stdin);
// freopen("ans.txt", "w", stdout);
int TestCase = 1;
//cin>>TestCase;
while (TestCase--)
{
solve();
}
}