4
27
2015
2

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: 2835
C_SUNSHINE 说:
2015年4月28日 21:23

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

cleaning companies d 说:
2020年2月23日 13:26

Considering small companies looking for one professional cleaning agency? Do you now have the tight funding? Do not even worry, it is easy to afford the application easily. Considering the increasing interest, the lots of service carriers has more than doubled. The maximizing number has generated a very difficult competition some of the service presenting companies. These have helped that service seekers acquire a cleaning product at competitively priced prices. The majority offer competent cleaning services around the affordable quotes.


登录 *


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