天津武清网站建设,网站被黑了怎么办,怎么挑选网站建设公司,丫丫影院正题 题目大意
要求支持区间乘和区间求∏φ(xi)\prod \varphi(x_i)∏φ(xi) 解题思路
首先φ(n)n∗∏(pi−1pi)\varphi(n)n*\prod (\frac{p_i-1}{p_i})φ(n)n∗∏(pipi−1) 我们定义xl,rx_{l,r}xl,r表示l∼rl\sim rl∼r的乘积ci,l,rc_{i,l,r}ci,l,r为l∼rl\sim r…正题 题目大意
要求支持区间乘和区间求∏φ(xi)\prod \varphi(x_i)∏φ(xi) 解题思路
首先φ(n)n∗∏(pi−1pi)\varphi(n)n*\prod (\frac{p_i-1}{p_i})φ(n)n∗∏(pipi−1) 我们定义xl,rx_{l,r}xl,r表示l∼rl\sim rl∼r的乘积ci,l,rc_{i,l,r}ci,l,r为l∼rl\sim rl∼r区间中包含质因数pip_ipi的数字个数。 然后答案显然可以转化为 xl,r∗∏((pi−1)ci,l,rpici,l,r)x_{l,r}*\prod(\frac{(p_i-1)^{c_{i,l,r}}}{p_i^{c_{i,l,r}}})xl,r∗∏(pici,l,r(pi−1)ci,l,r)
然后xl,rx_{l,r}xl,r和ci,l,rc_{i,l,r}ci,l,r都可以用线段树维护。
由于xi≤600x_i\leq 600xi≤600所以质因数数量是109109109个。
加上一个区间乘的线段树。
所以时间复杂度为:O(110∗(qlogn))O(110*(q\log n))O(110∗(qlogn)) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
struct Treenode{ll l,r,w,lazy;
};
const ll N1e41e2,XJQ100000007;
ll n,a[N],m,pri[600],cnt;
bool v[600];
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
struct Line_Cut_Tree{Treenode t[N*4];void build(ll x,ll l,ll r,ll val){t[x].ll;t[x].rr;if(lr){t[x].w(a[l]%val0);return;}ll mid(lr)/2;build(x*2,l,mid,val);build(x*21,mid1,r,val);t[x].wt[x*2].wt[x*21].w;}void downdata(ll x){if(!t[x].lazy) return;t[x*2].wt[x*2].r-t[x*2].l1;t[x*2].lazy1;t[x*21].wt[x*21].r-t[x*21].l1;t[x*21].lazy1;t[x].lazy0;}ll ask(ll x,ll l,ll r){if(t[x].llt[x].rr)return t[x].w;downdata(x);if(rt[x*2].r) return ask(x*2,l,r);else if(lt[x*21].l) return ask(x*21,l,r);else return ask(x*2,l,t[x*2].r)ask(x*21,t[x*21].l,r);t[x].wt[x*2].wt[x*21].w;}void change(ll x,ll l,ll r){if(t[x].llt[x].rr){t[x].lazy1;t[x].wt[x].r-t[x].l1;return;}downdata(x);if(rt[x*2].r) change(x*2,l,r);else if(lt[x*21].l) change(x*21,l,r);else change(x*2,l,t[x*2].r),change(x*21,t[x*21].l,r);t[x].wt[x*2].wt[x*21].w;}
}Tree[120];
struct Line_Cut_Tree2{Treenode t[N*4];void build(ll x,ll l,ll r){t[x].lazy1;t[x].ll;t[x].rr;if(lr){t[x].wa[l];return;}ll mid(lr)/2;build(x*2,l,mid);build(x*21,mid1,r);t[x].wt[x*2].w*t[x*21].w%XJQ;}void downdata(ll x){if(t[x].lazy1) return;ll L1t[x*2].r-t[x*2].l1,L2t[x*21].r-t[x*21].l1;t[x*2].wt[x*2].w*power(t[x].lazy,L1)%XJQ;t[x*2].lazyt[x*2].lazy*t[x].lazy%XJQ;t[x*21].wt[x*21].w*power(t[x].lazy,L2)%XJQ;t[x*21].lazyt[x*21].lazy*t[x].lazy%XJQ;t[x].lazy1;}ll ask(ll x,ll l,ll r){if(t[x].llt[x].rr)return t[x].w;downdata(x);if(rt[x*2].r) return ask(x*2,l,r);else if(lt[x*21].l) return ask(x*21,l,r);else return ask(x*2,l,t[x*2].r)*ask(x*21,t[x*21].l,r)%XJQ;t[x].wt[x*2].w*t[x*21].w%XJQ;}void change(ll x,ll l,ll r,ll val){if(t[x].llt[x].rr){(t[x].lazy*val)%XJQ;(t[x].w*power(val,r-l1))%XJQ;return;}downdata(x);if(rt[x*2].r) change(x*2,l,r,val);else if(lt[x*21].l) change(x*21,l,r,val);else change(x*2,l,t[x*2].r,val),change(x*21,t[x*21].l,r,val);t[x].wt[x*2].w*t[x*21].w%XJQ;}
}Tre;
void Prime(ll x)
{for(ll i2;ix;i){if(v[i]) continue;pri[cnt]i;for(ll ji;jx;ji)v[j]1;}for(ll i1;icnt;i)Tree[i].build(1,1,n,pri[i]);
}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]);Tre.build(1,1,n);Prime(600);scanf(%lld,m);for(ll i1;im;i){ll c,l,r,x,L;scanf(%lld%lld%lld,c,l,r);Lr-l1;if(c){ll ans1,del1;for(ll j1;jcnt;j){int ETree[j].ask(1,l,r);(ans*power(pri[j]-1,E))%XJQ;(del*power(pri[j],E))%XJQ;}(ans*Tre.ask(1,l,r))%XJQ; (ans*power(del,XJQ-2))%XJQ;printf(%lld\n,ans);}else{scanf(%lld,x);for(ll j1;jcnt;j)if(!(x%pri[j]))Tree[j].change(1,l,r);Tre.change(1,l,r,x);}}
}
