【JZOJ4638】第三条跑道

2023-10-25 03:08
文章标签 跑道 jzoj4638 第三条

本文主要是介绍【JZOJ4638】第三条跑道,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

这里写图片描述

Solution

这题码农,表示又被出题人虐了

我们发现 ai 以及 x 都小于等于600,于是我们可以分解质因数,我们看看部分质数表:
这里写图片描述
这说明600以内的指数只有109个(那么这里有只HowarLi翻车了)。

于是我们用线段树,对于每个区间记录109个质数被该区间多少个数包含。

由于要区间修改,我们再记录109个lazy,表示该区间该质数还要下传多少次。

那么,现在我们知道 φ(n)=nmi=1(11pi) pi 表示的 n 质因数,m表示质因数的种数)。

观察上面的式子,一个很显然的结论是 φ(pn)=pφ(n)(p|n) (这里 p 是质因数)

那如果p不是 n 的质因数呢?

那么φ(pn)=p(11p)φ(n)=(p1)φ(n)

那么至于区间乘上一个数 x ,先给它分解质因数,得出mi=1xkii=x

对于一个质因数 xi ,我们已知该区间有 Axi 个数包含它,那么它们对欧拉积的贡献为: xAxii

但是,没有包含的怎么办?由上可得,没有包含的将乘上一个 (xi1) ,所以该区间没有被包含的对欧拉积的贡献就为: (xi1)rl+1Axi

最后给修改的区间打上 lazy 标记即可。

但是,怎样下传标记?

我们对于一个区间有 lazyi 表示第 i 个质数还要下传多少次。那么,我们先给这个区间下传一次,具体下传请看上述修改部分。然后,由于还要下传(lazyi1)次,而且因为已经下传过一次,所以整个区间都有包含了第 i 个质数,剩下的贡献就为:(prrl+1i)lazyi1(这里 pri 表示第 i 个质数)。

对于查询,直接找到区间欧拉积即可。

时间复杂度:O(109nlog22n)

然而,这题看似容易,实际上打对调对需要花费大量时间。

可以打一个线性筛法求 φ <script type="math/tex" id="MathJax-Element-29">φ</script>来方便调试。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define N 10010
#define M 601
#define mo 100000007
#define ll long long
using namespace std;
int pr[M],cnt=0,phi[M];
int a[N];
bool bz[M];
struct node{int a[120];int lz[120];ll s;
}tr[N*4];
int ph[N],s1[N],s2[N];
int ls[120];
int map[M];
ll pow(ll m,int n)
{ll b=1;while(n){if(n%2==1)  b=b*m%mo;n/=2;m=m*m%mo;}return b;
}
void pre()
{int cnt=0;for(int i=2;i<M;i++){if(!bz[i]) pr[++cnt]=i,map[i]=cnt,phi[i]=i-1;for(int j=1;j<=cnt && i*pr[j]<M;j++){bz[i*pr[j]]=true;            if(i%pr[j]==0){phi[i*pr[j]]=phi[i]*pr[j];break;}else phi[i*pr[j]]=phi[i]*(pr[j]-1);}}
}
void get(int v,int x)
{int z=0,t=x;while(x){z++;if(pr[z]*pr[z]>t) break;if(x%pr[z]==0){tr[v].a[map[pr[z]]]=1;while(x%pr[z]==0) x/=pr[z];}}if(x>1) tr[v].a[map[x]]=1;
}
void getlazy(int v,int x)
{int z=0,t=x;while(x){z++;if(pr[z]*pr[z]>t) break;if(x%pr[z]==0){while(x%pr[z]==0) tr[v].lz[map[pr[z]]]++,ls[map[pr[z]]]++,x/=pr[z];}}if(x>1) tr[v].lz[map[x]]++,ls[map[x]]++;
}
void put(int v,int l,int r)
{int mid=(l+r)/2;fo(i,1,109){if(!tr[v].lz[i]) continue;tr[v*2].s=tr[v*2].s*pow(pr[i],tr[v*2].a[i])%mo*pow(pr[i]-1,mid-l+1-tr[v*2].a[i])%mo;tr[v*2+1].s=tr[v*2+1].s*pow(pr[i],tr[v*2+1].a[i])%mo*pow(pr[i]-1,r-mid-tr[v*2+1].a[i])%mo;tr[v*2].a[i]=mid-l+1;tr[v*2+1].a[i]=r-mid;tr[v*2].s=tr[v*2].s*pow(pow(pr[i],mid-l+1),tr[v].lz[i]-1)%mo;tr[v*2+1].s=tr[v*2+1].s*pow(pow(pr[i],r-mid),tr[v].lz[i]-1)%mo;tr[v*2].lz[i]+=tr[v].lz[i];tr[v*2+1].lz[i]+=tr[v].lz[i];tr[v].lz[i]=0;}
}
void build(int v,int l,int r)
{if(l==r){get(v,a[l]);tr[v].s=phi[a[l]];return;}int mid=(l+r)/2;build(v*2,l,mid);build(v*2+1,mid+1,r);fo(i,1,109)tr[v].a[i]=tr[v*2].a[i]+tr[v*2+1].a[i];tr[v].s=tr[v*2].s*tr[v*2+1].s%mo;
}
void change(int v,int l,int r,int x,int y,int p)
{if(l==x && r==y){getlazy(v,p);fo(i,1,109)if(ls[i]){tr[v].s=tr[v].s*pow(pr[i],tr[v].a[i])%mo*pow(pr[i]-1,r-l+1-tr[v].a[i])%mo;tr[v].a[i]=r-l+1;tr[v].s=tr[v].s*pow(pow(pr[i],r-l+1),ls[i]-1)%mo;ls[i]=0;}return;}put(v,l,r);int mid=(l+r)/2;if(y<=mid) change(v*2,l,mid,x,y,p);else if(x>mid) change(v*2+1,mid+1,r,x,y,p);else{change(v*2,l,mid,x,mid,p);change(v*2+1,mid+1,r,mid+1,y,p);}fo(i,1,109)tr[v].a[i]=tr[v*2].a[i]+tr[v*2+1].a[i];tr[v].s=tr[v*2].s*tr[v*2+1].s%mo;
}
ll ans=1;
void find(int v,int l,int r,int x,int y)
{if(l==x && r==y){ans=ans*tr[v].s%mo;return;}int mid=(l+r)/2;put(v,l,r);if(y<=mid) find(v*2,l,mid,x,y);else if(x>mid) find(v*2+1,mid+1,r,x,y);else{find(v*2,l,mid,x,mid);find(v*2+1,mid+1,r,mid+1,y);}
}
int main()
{freopen("2.in","r",stdin);freopen("2.out","w",stdout);pre();phi[1]=1;int n,T;cin>>n;fo(i,1,n) scanf("%d",&a[i]);build(1,1,n);cin>>T;while(T--){int z,l,r;scanf("%d %d %d",&z,&l,&r);if(!z){int x;scanf("%d",&x);change(1,1,n,l,r,x);}else{ans=1;find(1,1,n,l,r);printf("%lld\n",ans);}}
}

这篇关于【JZOJ4638】第三条跑道的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/279597

相关文章

智力题:25匹马5条跑道找最快的3匹马,最少需要跑几次?

要找出25匹马中最快的3匹马,使用5条跑道,最少需要跑几次?我们可以通过逐步推理来解决这个问题。 第一步:分组比赛 首先,我们将25匹马分成5组,每组5匹马。每组进行一次比赛,这样我们就有5次比赛的结果。 组1:A1, A2, A3, A4, A5 组2:B1, B2, B3, B4, B5 组3:C1, C2, C3, C4, C5 组4:D1, D2, D3, D4, D5 组

为人处事电影解说,全新升级瀚海跑道一分钟一条视频,全平台可推广,轻轻松松日入1000

自古以来,我国流行的一种现象是,大多数人都会与领导或上司打交道。由于某些话题不宜公开讨论,因此出现了许多含蓄的表达方式。随着年龄的增长,人们的态度也发生了变化,从最初的轻视到现在的重视。 下 载 地  址:laoa1.cn/1846.html 这种现象本身就具有话题性,因此很多人会在短视频下面进行评论和讨论,无论是讽刺还是其他。我们制作这类短视频,就是利用这种争议性话题,通过人们对为人处事的不

2024全新瀚海跑道:矢量图片迅速养号游戏玩法,每天一小时,日转现200

最初我注意到这种玩法,是因为最近在浏览各大平台的视频时,我发现了一种特殊类型的账号,其养号成功率高达90%。这些账号发布的视频内容和数据非常夸张,而且制作起来非常简单,任何人都可以轻松上手。这些账号主要发布矢量图片风格的视频,这类账号的特点是原创作者较少,非常适合新手快速加入。 下载 地  址 : laoa1.cn/1830.html 而且,这些账号可以在手机或电脑上操作,对于没有电脑的朋

luceda ipkiss教程 41:画跑道型微环

利用picazzo库中的方向耦合器绘制跑道型微环: from si_fab import all as pdkfrom ipkiss3 import all as i3from picazzo3.wg.dircoup import StraightDirectionalCouplerclass RingResonator(i3.PCell):trace_template = i3.Tra

luceda ipkiss教程 41:画跑道型微环

利用picazzo库中的方向耦合器绘制跑道型微环: from si_fab import all as pdkfrom ipkiss3 import all as i3from picazzo3.wg.dircoup import StraightDirectionalCouplerclass RingResonator(i3.PCell):trace_template = i3.Tra

运动员分组比赛;有N个人参加100米短跑比赛,有8条跑道,如何分组使分组数目最少且每组人数相差最少。

#include<iostream>using namespace std;#define N 8int main(){int m;cout<<"输入人数"<<endl;cin>>m;if(m<=N){cout<<"一组"<<m<<"人"<<endl;}else if(m%8==0){cout<<"一组"<<m/8<<"人"<<endl;}else{int i=m/8+1;int j=m/

Java、求出跑道长度

假设一个飞机的加速度是a 而起飞速度是 v ,那么可以使用下面的公式计算出飞机起飞所需的最短跑道长度:                         跑道长度 = v^2 / (2a) 编写程序,提示用户输入以米/秒(m/s)为单位的速度 v 和以米/秒的平方(m/s^2)为单位的加速度 a ,然后显示最短跑道长度。 package pack2;import java.

25匹赛马5个跑道算法

25匹赛马,5个跑道,也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马 ?

matlab 小球,Matlab 小球绕跑道运动

发布时间: Oct 21, 2012 更新时间: Oct 21, 2012 总字数:210 阅读时间:1m 作者: 谢先斌 Matlab 小球绕跑道运动 代码 figure('numbertitle','off','name','Matlab Animation Demo--matlabfan','MenuBar','none') prompt={'请输入速度v','请输入长度L','请输入半径

25匹马5个跑道,选出最快的5匹马?

回顾之前问题:25匹马5个跑道,怎样选出最快的3匹? 答:先分成5组比赛并组内排序(从1到5速度减慢),再让每组第一名比赛,按照每组第一名的比赛结果从快到慢对每组排序(从A到E速度减慢),此时共计比赛6轮,有: A1 A2 A3 A4 A5 -> A组 B1 B2 B3 B4 B5 -> B组 C1 C2 C3 C4 C5 -> C组 D1 D2 D3 D4 D5 -> D组 E1 E2 E3 E