[题目链接]
https://codeforces.com/contest/920/problem/F
[算法]
显然 ， 一个10 ^ 6以内的数在经过最多6次操作后就会变为1或2 ， 这是因为一个数的因子个数是根号级别的
用筛法预处理10 ^ 6以内每个数的因数个数 ， 用线段树维护即可 ， 修改时可以暴力地修改到叶子节点
时间复杂度 : O(NlogN)
[代码]
#include<bits/stdc++.h> using namespace std; const int MAXN = 3e5 + 10; const int MAXP = 1e6 + 10; typedef long long ll; typedef long double ld; int n , m; int val[MAXN] , p[MAXP]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } struct Segment_Tree { struct Node { int l ,r; ll cnt; bool flg; } a[MAXN << 2]; inline void build(int index , int l , int r) { a[index].l = l , a[index].r = r; if (l == r) { a[index].cnt = val[l]; a[index].flg = (a[index].cnt == 1 || a[index].cnt == 2); return; } int mid = (l + r) >> 1; build(index << 1 , l , mid); build(index << 1 | 1 , mid + 1 , r); update(index); } inline bool update(int index) { a[index].flg = a[index << 1].flg & a[index << 1 | 1].flg; a[index].cnt = a[index << 1].cnt + a[index << 1 | 1].cnt; } inline void modify(int index , int l , int r) { int mid =(a[index].l + a[index].r) >> 1; if (a[index].flg) return; if (a[index].l == l && a[index].r == r) { if (l == r) { a[index].cnt = p[a[index].cnt]; a[index].flg = (a[index].cnt == 1 || a[index].cnt == 2); return; } else { modify(index << 1 , l , mid); modify(index << 1 | 1 , mid + 1 , r); update(index); } return; } if (mid >= r) modify(index << 1 , l , r); else if (mid + 1 <= l) modify(index << 1 | 1 , l , r); else { modify(index << 1 , l , mid); modify(index << 1 | 1 , mid + 1 , r); } update(index); } inline ll query(int index , int l , int r) { if (a[index].l == l && a[index].r == r) return a[index].cnt; else { int mid = (a[index].l + a[index].r) >> 1; if (mid >= r) return query(index << 1 , l , r); else if (mid + 1 <= l) return query(index << 1 | 1 , l , r); else return query(index << 1 , l , mid) + query(index << 1 | 1 , mid + 1 , r); } } } SGT; int main() { read(n); read(m); for (int i = 1; i < MAXP; i++) { for (int j = i; j < MAXP; j += i) ++p[j]; } for (int i = 1; i <= n; i++) read(val[i]); SGT.build(1 , 1 , n); for (int i = 1; i <= m; i++) { int type; read(type); if (type == 1) { int l , r; read(l); read(r); SGT.modify(1 , l , r); } else { int l , r; read(l); read(r); printf("%lld " , SGT.query(1 , l , r)); } } return 0; }