数学题-白红宇

数学题

阅读量：4602 次

发布时间：2019-06-09

本文共 3032 字，大约阅读时间需要 10 分钟。

题目背景

你喜欢数学吗！（反正我不喜欢）

不管你喜不喜欢！这是一道数学题！

题目描述

定义一个函数d(x)为x的约数个数。例如，d(4) = 3,d(12) = 6。

有n个数a1,a2,...,an，对它们进行两种操作：

1 l r：对所有i∈[l,r]，将ai变成d(ai)。

2 l r：输出[l,r]的区间和。

输入输出格式

输入格式

第一行两个整数n和m，分别表示序列a的长度和操作次数。

第二行n个整数，表示序列a的初值。

接下来m行每行三个整数表示操作，格式见“题目描述”。

输出格式

对于每个操作2，输出一行答案。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
           7 #define space putchar(' ') 8 #define enter putchar('\n') 9 typedef long long ll; 10 using namespace std; 11 template 
           
             12 void read(T &x){ //读入优化啊 13 char c; 14 bool op = 0; 15 while(c = getchar(), c < '0' || c > '9') 16 if(c == '-') op = 1; 17 x = c - '0'; 18 while(c = getchar(), c >= '0' && c <= '9') 19 x = x * 10 + c - '0'; 20 if(op) x = -x; 21 } 22 template 
            
              23 void write(T x){ //又写读入优化又写输出优化的奆佬学姐 24 if(x < 0) putchar('-'), x = -x; 25 if(x >= 10) write(x / 10); 26 putchar('0' + x % 10); 27 } 28 29 const int N = 1e6 + 6, M = 3e5 + 6; 30 int n, m; 31 int prime[N], d[N], t[N]; 32 bool p[N]; 33 void init(int n){ 34 d[1]=1; t[1]=0; 35 for (int i=2;i<=n;++i){ 36 if(!p[i]) prime[++prime[0]]=i, d[i]=2, t[i]=1; 37 for (int j=1;j<=prime[0] && i*prime[j] <= n;++j){ 38 p[i*prime[j]]=1; 39 if (!(i%prime[j])){ 40 d[i*prime[j]]=d[i]/(t[i]+1)*(t[i]+2); 41 t[i*prime[j]]=t[i]+1; 42 break; 43 } 44 else{ 45 d[i*prime[j]]=d[i]*2; 46 t[i*prime[j]]=1; 47 } 48 } 49 } 50 } 51 ll data[4 * M]; 52 int mx[4 * M], a[M]; 53 bool done[4 * M]; 54 55 void build(int k, int l, int r){ //种树 56 if(l == r){ 57 data[k] = mx[k] = a[l]; 58 if(mx[k] <= 2) done[k] = 1; 59 return; 60 } 61 int mid = (l + r) >> 1; 62 build(k << 1, l, mid); 63 build(k << 1 | 1, mid + 1, r); 64 data[k] = data[k << 1] + data[k << 1 | 1]; 65 mx[k] = max(mx[k << 1], mx[k << 1 | 1]); 66 if(mx[k] <= 2) done[k] = 1; 67 } 68 void change(int k, int l, int r, int ql, int qr){ //这就是那个求约数个数的骚操作 69 if(l == r){ 70 data[k] = mx[k] = d[data[k]]; 71 if(mx[k] <= 2) done[k] = 1; 72 return; 73 } 74 int mid = (l + r) >> 1; 75 if(ql <= mid && !done[k << 1]) change(k << 1, l, mid, ql, qr); 76 if(qr > mid && !done[k << 1 | 1]) change(k << 1 | 1, mid + 1, r, ql, qr); 77 data[k] = data[k << 1] + data[k << 1 | 1]; 78 mx[k] = max(mx[k << 1], mx[k << 1 | 1]); 79 if(mx[k] <= 2) done[k] = 1; 80 } 81 ll query(int k, int l, int r, int ql, int qr){ //这是求和 82 if(ql <= l && qr >= r) return data[k]; 83 int mid = (l + r) >> 1; 84 ll ret = 0; 85 if(ql <= mid) ret += query(k << 1, l, mid, ql, qr); 86 if(qr > mid) ret += query(k << 1 | 1, mid + 1, r, ql, qr); 87 return ret; 88 } 89 90 int main(){ 91 freopen("math.in","r",stdin);freopen("math.out","w",stdout); 92 init(1e6 + 3); 93 read(n), read(m); 94 for(int i = 1; i <= n; i++) read(a[i]); 95 build(1, 1, n); 96 int op, l, r; 97 while(m--){ 98 read(op), read(l), read(r); 99 if(op == 1) change(1, 1, n, l, r);100 else write(query(1, 1, n, l, r)), enter;101 }102 103 return 0;104 }