4
27
2015
1

bzoj 4026:dC Loves Number Theory

Number Theory个球球。。。。

出题人不知为何加了6000B什么鬼东西。。。7k+差评。。。

题意:询问一段区间数积的$\varphi$

数列大小50000,询问100000,每个数大小$\leq 1000000$,答案模$1e6+777$

考虑$\varphi$怎么求的。。。

显然是$n\prod (1-\frac{1}{p_{i}})$

n好求,预处理个逆元就好了。

后面的其实是一段区间内只出现一次的质数的代价,我们定义一个质数$p$的代价为$1-\frac{1}{p}$

经典问题,首先分解质因数,一个数最多分解为7个质因子,然后一个主席树搞搞就好。

时间复杂度$O(nlogn)$

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

typedef long long LL;

const int N=400000,M=15000000,Mod=1000777;

struct Node
{
	int lc,rc,W;
}T[M];

int q,n,m,tot,rt[N],k1[N],k2[N],pos[N],Ed[N],Ni[Mod],last[Mod],suc[N],Ans;

#define Mid (l+r>>1)

void Add(int& x,int l,int r,int L,int R,int k)
{
	int y=x;
	x=++tot;
	T[x]=T[y];
	if(L<=l&&r<=R)
		T[x].W=T[x].W*(LL)k%Mod;
	else
	{
		if(L<=Mid)
			Add(T[x].lc,l,Mid,L,R,k);
		if(R>Mid)
			Add(T[x].rc,Mid+1,r,L,R,k);
	}
}

int Ask(int x,int l,int r,int p)
{
	if(!x)
		return 1;
	if(l==r)
		return T[x].W;
	return T[x].W*(LL)(p<=Mid?Ask(T[x].lc,l,Mid,p):Ask(T[x].rc,Mid+1,r,p))%Mod;
}

int main()
{
	scanf("%d%d",&n,&q);
	Ni[1]=1;
	for(int i=2;i<Mod;i++)
		Ni[i]=(Mod-(Mod/i)*(LL)Ni[Mod%i]%Mod)%Mod;
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		pos[i]=m+1;
		if(a==1)
			Ed[i]=m;
		else
		{
			pos[i]=m+1;
			for(int j=2;j*j<=a;j++)
				if(a%j==0)
				{
					k1[++m]=j;
					k2[m]=1;
					while(a%j==0)
						a/=j,k2[m]=k2[m]*(LL)j%Mod;
				}
			if(a>1)
				k1[++m]=a,k2[m]=a;
			Ed[i]=m;
		}
	}
	k2[0]=1;
	for(int i=1;i<=m;i++)
		k2[i]=k2[i-1]*(LL)k2[i]%Mod;
	T[0].W=1;
	for(int i=m;i>=1;i--)
	{
		if(last[k1[i]])
			suc[i]=last[k1[i]];
		else
			suc[i]=m+1;
		last[k1[i]]=i;
		rt[i]=rt[i+1];
		Add(rt[i],1,m,i,suc[i]-1,Mod+1-Ni[k1[i]]);
	}
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		l^=Ans;r^=Ans;
		Ans=1;
		if(pos[l]<=Ed[r])
			Ans=k2[Ed[r]]*(LL)Ni[k2[pos[l]-1]]%Mod*Ask(rt[pos[l]],1,m,Ed[r])%Mod;
		printf("%d\n",Ans);
	}
	return 0;
}
Category: My Oi,My Life | Tags: bzoj 逗比 | Read Count: 1014
C_SUNSHINE 说:
2015年4月28日 21:23

为什么您数据结构那么强啊


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com