Problem E E 、 小 花梨 的数组
时间限制：1000ms 空间限制：512MB
Description
小花梨得到了一个长度为𝑜的数组𝑏，现在要对它进行三种操作：
⚫ 1 𝑠 ] ∗
⚫ 2 𝑚 𝑠 对所有的𝑗 ∈ [𝑚,𝑠],𝑏[𝑗] = 𝑏[𝑗] / 𝑛𝑗𝑜𝑞𝑠𝑗𝑛𝑓(𝑏[𝑗])
⚫ 3 𝑦 求𝑏[𝑦]的值
𝑛𝑗𝑜𝑞𝑠𝑗𝑛𝑓(𝑦) = {
1 (𝑦 = 1)
𝑦的最小素因子(𝑦 ≥ 2)
现在给出初始数组𝑏，对其进行𝑛次操作，对于第三种操作输出结果。
Input
第一两个正整数𝑜,𝑛，表示数组的长度以及操作次数(1 ≤ 𝑜,𝑛 ≤ 100000)
第二行输入𝑜个正整数表示数组𝑏(1 ≤ 𝑏 𝑗 ≤ 1000000)
接下来𝑛行表示𝑛次操作，每行输入格式为"1 𝑚 𝑠"或者"2 𝑚 𝑠"，或者"3 𝑦"，对应上述三种操作。
1 ≤ 𝑚,𝑠,𝑦 ≤ 𝑜,𝑚 ≤ 𝑠
Output
对于第三种操作输出答案即可，答案对10 9 + 7进行取模。
Example
Sample Input Sample Output
5 8
1 2 3 4 5
1 2 4
3 2
3 3
2 2 5
3 2
3 5
1 5 5
3 5
4
9
2
1
1
题意：
思路：
读入的时候用唯一分解定理将a[i]分解为每一个质因子放入一个堆中。
我们知道一个数乘以它的最小的质因子后，它的最小的质因子不会改变。
如果先乘后除以它的最小的质因子，那么就是除以抵消一次乘法。那么我们可以标记一个数当前需要操作1多少次laze1，而不去实际更新数值，那么如果需要操作2的时候，laze1>0,那么影响只是laze1--，否则就是 需要执行的操作2次数laze2++.
我们用线段树来处理区间操作的问题，
那么我们再来分析一下单点询问是，该如何得到答案，我们知道，如果一个点的laze2有数值，laze2也有数值，那么这些除法操作一定在乘法操作之前，至于为什么，看上面laze变化的讲解。所以我们可以先暴力除掉需要除掉的数，当数值等于1的时候停止。（因为没有意义，又因为唯一分解定理可以知道一个小于等于1e6的数最多被除以十几次而已），除以之后得到的剩余数值a[i] *它的最小质因子的laze1次幂就是当前的a[i]数值。
线段树的pushdown 同样根据上面的性质和优先级进行处理。
细节见代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int *p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
// const int maxn = 1e7+50;
bool noprime[maxn + 50];
vector <int> p;
int getPrime()
{
// 华丽的初始化
memset(noprime, false, sizeof(noprime));
p.clear();
int m = (int)sqrt(maxn + 0.5);
// 优化的埃筛
for (int i = 2; i <= m; i++) {
if (!noprime[i]) {
for (int j = i * i; j <= maxn; j += i) {
noprime[j] = true;
}
}
}
// 把素数加到vector里
for (int i = 2; i <= maxn; i++) {
if (!noprime[i]) {
p.push_back(i);
}
}
//返回vector的大小
return p.size();
}
ll pf[105][2];// 0 -> value 1->count
const int N = 1e5 + 10;
priority_queue<int, vector<int>, greater<int> > q[N];
const ll mod = 1e9 + 7;
void getPrifac( ll n, int len, int id)
{
int pos = 0;
for (int i = 0; 1ll * p[i]*p[i] <= n && i < len; i++) {
if ( n % p[i] == 0) {
// 算质因数的幂数
while (n % p[i] == 0) {
q[id].push(p[i]);
n /= p[i];
}
// q[id].push(temp);
}
}
if ( n > 1) {
// pf[++pos][0] = n;
// pf[pos][1]=1;
q[id].push((n));
}
// return pos; // 优美的返回有多少个质因数
// 1~pos
}
int n;
ll a[N];
struct node {
int l, r;
int laze1;
int laze2;
} segment_tree[N << 2];
void build(int rt, int l, int r)
{
segment_tree[rt].l = l;
segment_tree[rt].r = r;
segment_tree[rt].laze2 = 0;
segment_tree[rt].laze1 = 0;
if (l == r) {
return ;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
}
void pushdown(int rt)
{
int x = min(segment_tree[rt].laze2, segment_tree[rt << 1].laze1);
segment_tree[rt << 1].laze1 -= x;
segment_tree[rt << 1].laze2 += segment_tree[rt].laze2 - x;
segment_tree[rt << 1].laze1 += segment_tree[rt].laze1;
x = min(segment_tree[rt].laze2, segment_tree[rt << 1 | 1].laze1);
segment_tree[rt << 1 | 1].laze1 -= x;
segment_tree[rt << 1 | 1].laze2 += segment_tree[rt].laze2 - x;
segment_tree[rt << 1 | 1].laze1 += segment_tree[rt].laze1;
segment_tree[rt].laze1 = segment_tree[rt].laze2 = 0;
}
void update1(int rt, int l, int r)
{
if (segment_tree[rt].l >= l && segment_tree[rt].r <= r) {
segment_tree[rt].laze1++;
} else {
pushdown(rt);
int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;
if (l <= mid) {
update1(rt << 1, l, r);
}
if (r > mid) {
update1(rt << 1 | 1, l, r);
}
}
}
void update2(int rt, int l, int r)
{
if (segment_tree[rt].l >= l && segment_tree[rt].r <= r) {
if (segment_tree[rt].laze1) {
segment_tree[rt].laze1--;
} else {
segment_tree[rt].laze2++;
}
} else {
pushdown(rt);
int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;
if (l <= mid) {
update2(rt << 1, l, r);
}
if (r > mid) {
update2(rt << 1 | 1, l, r);
}
}
}
ll ask(int rt, int id)
{
if (segment_tree[rt].l == segment_tree[rt].r && segment_tree[rt].r == id) {
while (segment_tree[rt].laze2 && a[id] > 1 && q[id].size()) {
segment_tree[rt].laze2--;
a[id] /= q[id].top();
q[id].pop();
}
ll x = 1ll;
if (q[id].size()) {
x = q[id].top();
}
return (powmod(x, segment_tree[rt].laze1, mod) * a[id]) % mod;
} else {
pushdown(rt);
int mid = (segment_tree[rt].r + segment_tree[rt].l) >> 1;
if (id <= mid) {
return ask(rt << 1, id);
} else {
return ask(rt << 1 | 1, id);
}
}
}
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
int m;
int len = getPrime();
scanf("%d %d", &n, &m);
repd(i, 1, n) {
scanf("%lld", &a[i]);
getPrifac(a[i], len, i);
}
build(1, 1, n);
int op;
while (m--) {
scanf("%d", &op);
if (op == 1) {
int l, r;
scanf("%d %d", &l, &r);
update1(1, l, r);
} else if (op == 2) {
int l, r;
scanf("%d %d", &l, &r);
update2(1, l, r);
} else {
int x;
scanf("%d", &x);
printf("%lld\n", ask(1, x) );
}
}
return 0;
}
inline void getInt(int *p)
{
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
} else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
京公网安备 11010502036488号