调研园区网站建设工作,动漫制作专业电脑配置,一般网站的字体大小,微信网站建设费用传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn的序列aaa#xff0c;qqq个询问#xff0c;每次询问[l,r][l,r][l,r]内的lcmlcmlcm是多少#xff0c;对1e971e971e97取模。 n≤1e5,a≤2e5,q≤1e5n\le1e5,a\le2e5,q\le1e5n≤1e5,a≤2e5,…传送门 文章目录题意思路题意
给你一个长度为nnn的序列aaaqqq个询问每次询问[l,r][l,r][l,r]内的lcmlcmlcm是多少对1e971e971e97取模。
n≤1e5,a≤2e5,q≤1e5n\le1e5,a\le2e5,q\le1e5n≤1e5,a≤2e5,q≤1e5
思路
关于lcmlcmlcm对于两个数的lcmlcmlcm为了防止爆炸我们通常写成a/gcd(a,b)∗ba/gcd(a,b)*ba/gcd(a,b)∗b如果求1−n1-n1−n所有数的lcmlcmlcm并且要求取模而且a,ba,ba,b都比较大我们就不能这么求了考虑将其分解为质因子的形式。
考虑a∗b/gcd(a,b)a*b/gcd(a,b)a∗b/gcd(a,b)到底干了个什么事情其实他将a,ba,ba,b的每个质因子的幂次都取了maxmaxmax之后就得到了他们的lcmlcmlcm换句话说原本ap1x1p2x2...pnxnap_1^{x1}p_2^{x2}...p_n^{xn}ap1x1p2x2...pnxnbp1y1p2y2...pnynbp_1^{y1}p_2^{y2}...p_n^{yn}bp1y1p2y2...pnyn那么lcm(a,b)p1max(x1,y1)p2max(x2,y2)...pnmax(xn,yn)lcm(a,b)p_1^{max(x1,y1)}p_2^{max(x2,y2)}...p_n^{max(x_n,y_n)}lcm(a,b)p1max(x1,y1)p2max(x2,y2)...pnmax(xn,yn)因为gcd(a,b)gcd(a,b)gcd(a,b)是取了minminmin除去之后就剩maxmaxmax啦。
所以我们可以通过维护质因子的个数最后就快速幂一下就好。
如果带修的话需要挂到线段树上考虑值域ai≤2e5a_i\le 2e5ai≤2e5的情况我们可以对于≤500\le 500≤500的质数每个都建一颗线段树最多也就909090个左右让后对于其他的素数幂次一定都是111我们查询区间内不同的数的乘积用主席树维护一下即可对于909090个线段树我们只需要维护区间maxmaxmax即可。
还可以将909090棵线段树换成ststst表让后用charcharchar存这样能快点。
这个的复杂度O(n∗90∗logn)O(n*90*logn)O(n∗90∗logn)常数有点大虽然卡卡能过但是显然不优我们考虑更优解法。
考虑我们离线怎么做显然我们套路的将其按照右端点排序现在我们就固定了右端点左端点在lll由于lcmlcmlcm是单调不减的所以考虑一个单调性我们将其移动到l−1l-1l−1的话贡献是多少呢假设al−1a_{l-1}al−1有一个质因子ppp其幂次为xxx在[l,r][l,r][l,r]之间的ppp幂次为yyy假设此时xyxyxy那么显然他对lcmlcmlcm的贡献为px−yp^{x-y}px−y否则其没有贡献。
这启发了我们什么呢我们是否可以像线段树离线维护数出现的最后位置一样维护质因子出现的最后位置呢假设现在有两个位置ijijij质因子pix,pjyp_i^{x},p_j^{y}pix,pjy假设xyxyxy那么将iii位置的质因子都删去在jjj位置乘上pyp^ypy显然是最优的这样来看直接取最后的位置是没问题的但是如果xyxyxy这个时候按照上面说的我们就不会更新但是如果后面查询[j,pos][j,pos][j,pos]的时候由于我们没加上jjj位置质因子的贡献所以会导致答案错误。
所以我们考虑维护一下每个质因子的每个幂次出现的位置这样对于xyxyxy的情况相当于将iii位置除上个pyp_ypy变成px−yp^{x-y}px−y让后将jjj位置更新为pyp^ypy这样查询[j,pos][j,pos][j,pos]的时候不会丢掉jjj的贡献并且查询[x,y][x,y][x,y]的时候由于维护的是乘积即px−y∗pypxp^{x-y}*p^{y}p^xpx−y∗pypx也不会丢掉iii位置的最大值这样这个问题就完美解决了。
复杂度由aaa来确定由于每个数最多有不超过logalogaloga个质因子所以时间复杂度上界是O(nlog2n)O(nlog^2n)O(nlog2n)空间复杂度O(nlog2n)O(nlog^2n)O(nlog2n)。
// Problem: F. Boring Queries
// Contest: Codeforces - Codeforces Round #675 (Div. 2)
// URL: https://codeforces.com/contest/1422/problem/F
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N200010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N],pre[N];
int root[N],idx;
struct Node {int l,r;LL mul;
}tr[N*100];
int prime[2*N10],cnt,ne[2*N];
bool st[2*N10];void get_prime(int n)
{for(int i2;in;i){if(!st[i]) prime[cnt]i,ne[i]i;for(int j0;prime[j]n/i;j){st[prime[j]*i]true;ne[prime[j]*i]prime[j];if(i%prime[j]0) break; } }
} LL qmi(LL a,LL b) {LL ans1;while(b) {if(b1) ansans*a%mod;aa*a%mod;b1;}return ans%mod;
}void build(int u,int l,int r) {uidx; tr[u].mul1;if(lr) return;int mid(lr)1;build(tr[u].l,l,mid); build(tr[u].r,mid1,r);
}void insert(int p,int q,int l,int r,int pos,int val) {qidx; tr[q]tr[p];tr[q].mul*val; tr[q].mul%mod;if(lr) return;int mid(lr)1;if(posmid) insert(tr[p].l,tr[q].l,l,mid,pos,val);else insert(tr[p].r,tr[q].r,mid1,r,pos,val);
}LL query(int u,int l,int r,int ql,int qr) {if(!u) return 1;if(lqlrqr) return tr[u].mul;LL ans1,mid(lr)1;if(qlmid) ansans*query(tr[u].l,l,mid,ql,qr)%mod;if(qrmid) ansans*query(tr[u].r,mid1,r,ql,qr)%mod;return ans;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);get_prime(3e5);scanf(%d,n);build(root[0],1,n);for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i) {int nowa[i];root[i]root[i-1];while(now!1) {int fne[now];int invqmi(ne[now],mod-2);vectorPIIv;LL fun1;while(now%f0) {fun*f; now/f;if(pre[fun]) v.pb({pre[fun],inv});pre[fun]i;}insert(root[i],root[i],1,n,i,fun);LL all1;for(int j0;jv.size();j) {all*v[j].Y,all%mod;if(jv.size()-1||v[j].X!v[j1].X) insert(root[i],root[i],1,n,v[j].X,all),all1;}}}LL last0;scanf(%d,m);while(m--) {int l,r; scanf(%d%d,l,r);l(1ll*llast)%n1; r(1ll*rlast)%n1;if(lr) swap(l,r);printf(%lld\n,lastquery(root[r],1,n,l,r));} return 0;
}
/**/
