咖啡网站开发背景怎么写,湖南网页制作公司,手机网站模板 html,常德交通网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个序列aaa#xff0c;你需要实现两种操作#xff1a; (1)(1)(1) 将[l,r][l,r][l,r]的aia_iai都乘rrr。 (2)(2)(2) 求ϕ(∏ilrai)mod1e97\phi(\prod_{il}^ra_i)\bmod 1e97ϕ(∏ilrai)mod1e97 1…传送门 文章目录题意思路题意
给你一个序列aaa你需要实现两种操作
(1)(1)(1) 将[l,r][l,r][l,r]的aia_iai都乘rrr。
(2)(2)(2) 求ϕ(∏ilrai)mod1e97\phi(\prod_{il}^ra_i)\bmod 1e97ϕ(∏ilrai)mod1e97
1≤n≤4e5,1≤1≤2e5,1≤ai,r≤3001\le n\le 4e5,1\le 1\le 2e5,1\le a_i,r\le 3001≤n≤4e5,1≤1≤2e5,1≤ai,r≤300
思路
注意到a,ra,ra,r都很小300300300以内的质数最多有606060几个在llllll的范围内这就明示我们状压这几个质因子。
在考虑欧拉函数有个公式ϕ(x)x∗∏(p−1p)\phi(x)x*\prod(\frac{p-1}{p})ϕ(x)x∗∏(pp−1)其中ppp是xxx的质因子。
由于是求区间乘起来的欧拉函数利用上面的式子因为我们对xxx取模了所以需要将质因子状压成statestatestate其中111代表有000代表没有让后直接维护一下就行了求一下区间aaa的乘积以及区间内statestatestate最后乘上p−1p\frac{p-1}{p}pp−1即可。
注意需要提前状压成一个状态修改如果对每个质因子修改会徒增888的常数导致TLETLETLE。
由于用到了快速幂复杂度O(nlog2n)O(nlog^2n)O(nlog2n)。
如果求的欧拉函数是区间和我们就不能直接按照上面那样求了需要每个质因子分开来考虑贡献如果一个区间内所有数都含有这个质因子那么区间的欧拉函数直接乘上ppp即可否则需要递归子区间来判断。由于每个位置的每个质因子最多被添加一次所以复杂度是可以得到保证的。最终递归到叶子的时候还是没有这个质因子这个时候乘上p−1p-1p−1即可。
复杂度也是O(nlog2n)O(nlog^2n)O(nlog2n)
// Problem: F. Please, another Queries on Array?
// Contest: Codeforces - Codeforces Round #538 (Div. 2)
// URL: https://codeforces.com/contest/1114/problem/F
// Memory Limit: 256 MB
// Time Limit: 5500 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
#includebitset
#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 N400010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N];
struct Node {int l,r;LL ans,s,lazy1,lazy2;
}tr[N2];
int mp[400],tot;
LL f[310];
vectorintdiver[310];LL qmi(LL a,LL b) {LL ans1;while(b) {if(b1) ansans*a%mod;aa*a%mod;b1;}return ans%mod;
}void update(int u,LL x,LL y) {(tr[u].ans*qmi(x,Len(u)))%mod;tr[u].s|y;(tr[u].lazy1*x)%mod;tr[u].lazy2|y;
}void pushup(int u) {tr[u].ans(tr[L].ans*tr[R].ans)%mod;tr[u].str[L].s|tr[R].s;
}void pushdown(int u) {LL lazy1tr[u].lazy1; tr[u].lazy11;LL lazy2tr[u].lazy2; tr[u].lazy20;update(L,lazy1,lazy2); update(R,lazy1,lazy2);
}void build(int u,int l,int r) {tr[u]{l,r};tr[u].lazy11;tr[u].lazy20;if(lr) {tr[u].ans1; tr[u].s0;return;}build(L,l,Mid); build(R,Mid1,r);pushup(u);
}void change(int u,int l,int r,LL x,LL y) {if(tr[u].lltr[u].rr) {update(u,x,y);return;}pushdown(u);if(lMid) change(L,l,r,x,y);if(rMid) change(R,l,r,x,y);pushup(u);
}Node query(int u,int l,int r) {if(tr[u].lltr[u].rr) return tr[u];pushdown(u);if(rMid) return query(L,l,r);if(lMid) return query(R,l,r);Node ans,lsquery(L,l,r),rsquery(R,l,r);ans.ansls.ans*rs.ans%mod;ans.sls.s|rs.s;return ans;
}bool check(int x) {for(int i2;ix/i;i) if(x%i0) return false;return true;
}
char s[20];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);// cout400000*18*18*8endl;for(int i2;i300;i) if(check(i)) mp[i]tot,f[tot-1]qmi(i,mod-2)*(i-1)%mod;scanf(%d%d,n,m);int mx0;for(int i2;i300;i) {int xi;for(int j2;jx/j;j) {while(x%j0) diver[i].pb(j),x/j;}if(x1) diver[i].pb(x);}build(1,1,n);for(int i1;in;i) {scanf(%d,a[i]);LL state0;for(auto x:diver[a[i]]) state|1ll(mp[x]-1);change(1,i,i,a[i],state);}for(int i1;im;i) {int l,r,x; scanf(%s%d%d,s1,l,r);if(s[1]M) {scanf(%d,x);LL state0;for(auto xx:diver[x]) state|1ll(mp[xx]-1);change(1,l,r,x,state);} else {Node ansquery(1,l,r);for(int i0;itot;i) if(ans.si1) (ans.ans*f[i])%mod;printf(%lld\n,ans.ans);}}return 0;
}
/*
4e5*18*18*8
*/
