BZOJ 4026 dC Loves Number Theory 分块+十字链表/可持久化线段树

题目大意:给定1个序列,屡次询问某段区间乘积的φ值对1000777的模

我居然卡过去了233333
将序列分块,记录fi,j表示第i块左端点到第j个点中出现的所有质数pp?1p之积
每次询问[x,y],首先取出[x,y]区间内所有数的积,然后乘上fst,y(其中stx后面第1个块端点所在块)
现在还剩[x,l[st]]部份没有统计
由于106之内的数分解得到的不同的质因数最多只有7个,因此暴力枚举零碎部份的质数便可
现在对每一个质数我们需要判断是不是出现过
我们只需要判断这个质数下1次出现的位置是不是大于y便可
用10字链表弄1弄就能够了
时间复杂度O(7mn)

这固然不是正解- –
珍重生命,阔别卡常,我们来看正解吧

实际上我们要统计的就是[x,y]区间内所有出现过的质数pp?1p之积
我们想到了甚么?没错,HH的项链!
由于强迫在线,因此我们用可持久化线段树弄1弄就好了。时间复杂度O(mlogn)

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 50500
#define B 700
#define MOD 1000777
using namespace std;
struct abcd{
abcd *up,*rt;
int p,belong;
void* operator new (size_t)
{
static abcd mempool[M*7],*C=mempool;
return C++;
}
}*head[M],*last[80800];
int n,m,b,last_ans;
int a[M];
int prime[80800],tot;
long long inv[MOD];
int l[M],belong[M];
int prod[B][M];
void Linear_Shaker()
{
static bool not_prime[1001001];
int i,j;
for(i=2;i<=1000000;i++)
{
if(!not_prime[i])
prime[++tot]=i;
for(j=1;prime[j]*i<=1000000;j++)
{
not_prime[prime[j]*i]=true;
if(i%prime[j]==0)
break;
}
}
for(inv[1]=1,i=2;i<MOD;i++)
inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
}
abcd* Decomposition(int pos)
{
int i,n=a[pos];
abcd *re=0x0;
for(i=1;prime[i]*prime[i]<=n;i++)
if(n%prime[i]==0)
{
abcd *temp=new abcd;
temp->up=re;
temp->p=i;
temp->belong=pos;
if(last[i])
last[i]->rt=temp;
re=last[i]=temp;

while(n%prime[i]==0)
n/=prime[i];
}
if(n!=1)
{
i=lower_bound(prime+1,prime+tot+1,n)-prime;

abcd *temp=new abcd;
temp->up=re;
temp->p=i;
temp->belong=pos;
if(last[i])
last[i]->rt=temp;
re=last[i]=temp;
}
return re;
}
int Query(int x,int y)
{
int i,st=belong[x-1]+1,re=inv[a[x-1]]*a[y]%MOD;
abcd *temp;
if(y>=l[st])
re=(long long)re*prod[st][y]%MOD;
for(i=min(y,l[st]-1);i>=x;i--)
for(temp=head[i];temp;temp=temp->up)
if(!temp->rt||temp->rt->belong>y)
re=re*inv[prime[temp->p]]%MOD*(prime[temp->p]-1)%MOD;
return re;
}
namespace IStream{
const int L=1<<15;
char buffer[L],*S,*T;
inline char Get_Char()
{
if(S==T)
{
T=(S=buffer)+fread(buffer,1,L,stdin);
if(S==T) return EOF;
}
return *S++;
}
inline int Get_Int()
{
char c;
int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9')
re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
return re;
}
}
int main()
{
using namespace IStream;
int i,j,x,y;
abcd *temp;
cin>>n>>m;
b=200;
Linear_Shaker();
for(i=1;i<=n;i++)
{
a[i]=Get_Int();
head[i]=Decomposition(i);
}
for(a[0]=1,i=1;i<=n;i++)
a[i]=(long long)a[i]*a[i-1]%MOD;
for(i=1;i<=n;i++)
belong[i]=(i-1)/b+1;
for(i=1;i<=belong[n];i++)
l[i]=(i-1)*b+1;
l[i]=0x3f3f3f3f;

static int v[80800],ans;
for(j=1;j<=belong[n];j++)
{
ans=1;
for(i=l[j];i<=n;i++)
{
for(temp=head[i];temp;temp=temp->up)
if(v[temp->p]!=j)
{
v[temp->p]=j;
ans = ans * inv[prime[temp->p]] % MOD * (prime[temp->p]-1) % MOD ;
}
prod[j][i]=ans;
}
}

for(i=1;i<=m;i++)
{
x=Get_Int();
y=Get_Int();
x^=last_ans;
y^=last_ans;
printf("%d
"
,last_ans=Query(x,y));
}
//puts("Fuck♂You!");
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » BZOJ 4026 dC Loves Number Theory 分块+十字链表/可持久化线段树

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡