题目链接：https://qduoj.com/problem/825
Description
Onion的数论很差，所以作为数学大佬的lb给onion出了一道私家特训提高题
首先给出n，m，代表接下来会有n个数字和m个操作
操作op有两个类型：
当op==1的时候，会输入一个新的下标pos和数值values, 使得 A[pos]=values
当op==2的时候，会输入一个左端点left和一个右端点right,令 MUL=A[left]*A[left+1]*.....*A[right], 求解MUL的因子数目
对于每个操作2，你需要给出答案，由于答案可能会比较大，所以你输出的答案要对998244353进行取余。
Input
1<=n<=1e5
1<=m<=1e5
1<=Ai<=10
1<= p <=n
1<=v <=10
1<=l<=r<=n
Output
对于每一个操作2输出答案
注：每个答案占一行
Sample Input 1
4 2 2 2 2 7 2 1 1 1 4 4Sample Output 1
2
思路：很显然是一个线段树的题目，关键是如何处理求解区间积的因子数。
整数分解 又称素因数分解，是将一个正整数写成几个约数的乘积。
例如：对于一个整数a，可以分解为若干个素数b,c,d的乘积，即 a=(b^e)*(c^f)*(d^g)。
那么a的因子数为(e+1)*(f+1)*(g+1)。
因为1<=Ai<=10，所以用2,3,5,7这四个素数就能表示所有的Ai(1不用考虑)。
这样就转化为求解区间内2,3,5,7的个数。具体见代码。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <string> #define cla(a, sum) memset(a, sum, sizeof(a)) #define rap(i, m, n) for(int i=m; i<=n; i++) #define rep(i, m, n) for(int i=m; i>=n; i--) #define bug printf("???\n") using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; const int Inf = 0x3f3f3f3f; const double eps = 1e-8; const int maxn = 1e5+5; const int mod = 998244353; template <typename T> void read(T &x){ x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();} while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } int n,m; struct node{ int l,r; ll cnt[10]; }f[4*maxn]; int a[maxn]; void update(int ans,int c){ while(c%2==0) f[ans].cnt[2]++,c/=2; while(c%3==0) f[ans].cnt[3]++,c/=3; while(c%5==0) f[ans].cnt[5]++,c/=5; while(c%7==0) f[ans].cnt[7]++,c/=7; } void push_up(int ans){ f[ans].cnt[2]=f[ans<<1].cnt[2]+f[ans<<1|1].cnt[2]; f[ans].cnt[3]=f[ans<<1].cnt[3]+f[ans<<1|1].cnt[3]; f[ans].cnt[5]=f[ans<<1].cnt[5]+f[ans<<1|1].cnt[5]; f[ans].cnt[7]=f[ans<<1].cnt[7]+f[ans<<1|1].cnt[7]; } void build(int ans,int l,int r){ f[ans].l =l;f[ans].r =r; cla(f[ans].cnt ,0);//初始化 if(l==r){ update(ans,a[l]); return ; } int mid=(l+r)>>1; build(ans<<1,l,mid); build(ans<<1|1,mid+1,r); push_up(ans); } void change(int ans,int id,int val){ if(f[ans].l ==f[ans].r ){ cla(f[ans].cnt ,0);//修改的时候，注意将数组清零 update(ans,val); return ; } int mid=(f[ans].l +f[ans].r )>>1; if(id<=mid)change(ans<<1,id,val); else if(id>mid)change(ans<<1|1,id,val); push_up(ans); } node query(int ans,int l,int r){ if(f[ans].l >=l&&f[ans].r <=r){ return f[ans]; } int mid=(f[ans].l +f[ans].r )>>1; if(r<=mid)return query(ans<<1,l,r); else if(l>mid)return query(ans<<1|1,l,r); else{ node u=query(ans<<1,l,mid); node w,v=query(ans<<1|1,mid+1,r); w.cnt[2]=u.cnt[2]+v.cnt[2]; w.cnt[3]=u.cnt[3]+v.cnt[3]; w.cnt[5]=u.cnt[5]+v.cnt[5]; w.cnt[7]=u.cnt[7]+v.cnt[7]; return w; } } int main() { read(n);read(m); rap(i,1,n) read(a[i]); build(1,1,n); int op; while(m--){ int u,v; read(op);read(u);read(v); if(op==1){ change(1,u,v); } else if(op==2){ node w=query(1,u,v); ll sum=(w.cnt[2]+1)%mod*(w.cnt[3]+1)%mod*(w.cnt[5]+1)%mod*(w.cnt[7]+1)%mod; printf("%lld\n",sum); } } return 0; }
