[Ynoi2015] glory at this moment (Mo team + numerical divide and conquer + Pollard Ou rho)

Question: https://www.luogu.com.cn/problem/P5071

 

 

 

 

Title Solution

(๑̀ㅂ́́و✧) favorable comments on the topic (๑̀ㅂ́) ✧

٩ (๑◡๑๑๑) the first Ynoi ٩ (๑◡๑) in life

First, use PR to decompose the prime factor of all numbers

In the case of Mo team, the idea is relatively simple. By directly counting the number of all quality factors, we can work out the approximate number of the product

(of course, first discretize the quality factor and preprocess the inverse element)

But the average number of all data quality factors is log level

The complexity of Mo team's moving the endpoint once will become log

The total complexity is O(n*sqrt(m)*logN)

Can't pass...

Because the total query complexity of our team Mo is O(m)

But the modification complexity is O(n*sqrt(m)*logN)

So we need to find a way to average them

So we consider to divide the answer into two parts according to the size of the quality factor. If the quality factor is less than 500, there are only 95. We can preprocess the prefix sum and O (95) query first

If the remaining quality factor is greater than 500, you can add it directly with Mo team. It can be found that there are only three such quality factors at most. O(3) is modified

The total complexity is O (n * sqrt (m * 3 + m * 95)

In theory, it's OK

 

(next is the normal time of ghost animal card)

But it's still T...

Write a data generator

It was found that it was too slow to decompose the prime factor, and PR was stuck Why is Pollard Chu Rho so disheartened

After thinking about it, it seems that you can sift out the prime numbers of 1e7, and then try to divide them. On the way, you can use Miller's Robin to judge the numbers within 1e7 directly

If x is prime in the middle of the way, exit directly

Then WA5 T5...

It's WA and T, so autistic

It suddenly occurred to me that team Mo has an optimization of sorting by points, parity and even

All WA after adding

Start to write contra

Later, I found that I didn't complete all the quality factors when I decomposed them

After that, A

 

AC Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gi()
{
	char c;int num=0,flg=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
	return num*flg;
}
#define N 100005
#define M 500
const int mod=19260817;
int prime[1400005],tot;
int inv[500005];
bool vis[20000005];
void shai()
{
	vis[1]=1;
	int i,j;
	for(i=2;i<=20000000;i++){
		if(!vis[i])prime[++tot]=i;
		for(j=1;j<=tot;j++){
			int tmp=i*prime[j];
			if(tmp>20000000)break;
			vis[tmp]=1;
			if(i%prime[j]==0)break;
		}
	}
	inv[1]=inv[0]=1;
	for(i=2;i<=500000;i++)
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}

int pr[105],pcnt;
int a[N][5],cnt[N],hh[5*N],hcnt;
int sum[100][N];
inline int ksm(int x,int y,int p)
{
	int ret=1;
	while(y){
		if(y&1)ret=1ll*x*ret%p;
		y>>=1;x=1ll*x*x%p;
	}
	return ret;
}
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int bas[6]={3,7,37,79,97,19260817};
inline bool mler(int n)
{
	if(n<=20000000)return vis[n]^1;
	int r=n-1,t=0;
	while(!(r&1))r>>=1,t++;
	for(int i=0;i<6;i++){
		if(n==bas[i])return 1;
		int now,pre=ksm(bas[i],r,n);
		for(int k=0;k<t;swap(now,pre),k++)
			if((now=1ll*pre*pre%n)==1&&pre!=1&&pre!=n-1)
				return 0;
		if(pre!=1)return 0;
	}
	return 1;
}
/*inline int ab(int x){return x<0?-x:x;}
int rho(int n,int c)
{
	int i=1,j=0,x=rand()%(n-1)+1,y=x;
	int d=1,tmp=1;
	while(d==1){
		x=(1ll*x*x+c)%mod;
		tmp=1ll*tmp*ab(y-x)%mod;
		if(++j==i)i<<=1,y=x,d=gcd(tmp,n);
		if(!(j&127))d=gcd(tmp,n);
	}
	return d==n?rho(n,c+1):d;
}

void plar(int n)
{
	if(n==1)return;
	if(mler(n)){pr[++pcnt]=n;return;}
	int d=rho(n,3);
	plar(d);plar(n/d);
}*/
#define D 366
int tong[5*N],ans[N];
struct node{
	int l,r,id;
}q[N];
inline bool cmp(const node &x,const node &y){int t=(x.l)/D;return t<(y.l/D)||(t==(y.l/D)&&(((t&1)&&x.r<y.r)||(!(t&1)&&x.r>y.r)));}
inline int query(int l,int r)
{
	int ret=1;
	for(int i=1;i<=95;i++)
		ret=1ll*ret*(sum[i][r]-sum[i][l-1]+1)%mod;
	return ret;
}
//#include<ctime>
//double c1;
int main()
{
	//c1=clock();
	//freopen("1.in","r",stdin);
	
	srand(0);shai();
	int n,i,j,m,x,l,r,mul,tmp;
	n=gi();m=gi();
	for(i=1;i<=n;i++){
		x=gi();//printf("%d\n",i);
		bool flg;
		if(x>500&&mler(x)){
			a[i][++cnt[i]]=x;
			hh[++hcnt]=x;
			//printf("%d\n",x);
			continue;
		}
		for(j=1;j<=95&&x>1;j++){
			flg=0;
			while(x%prime[j]==0){
				sum[j][i]++;
				x/=prime[j];
				//printf("%d ",prime[j]);
				flg=1;
			}
		}
		if(x>500&&mler(x)){
			a[i][++cnt[i]]=x;
			hh[++hcnt]=x;
			//printf("%d\n",x);
			continue;
		}
		for(j=96;1ll*prime[j]*prime[j]<=x&&x>1;j++){
			flg=0;
			while(x%prime[j]==0){
				a[i][++cnt[i]]=prime[j];
				hh[++hcnt]=prime[j];
				//printf("%d ",prime[j]);
				x/=prime[j];
				flg=1;
			}
			if(flg&&mler(x))break;
		}
		if(x>500){
			a[i][++cnt[i]]=x;
			hh[++hcnt]=x;
		}
		//printf("%d\n",x);
		/*pcnt=0;plar(x);
		for(j=1;j<=pcnt;j++){
			a[i][++cnt[i]]=pr[j];
			hh[++hcnt]=pr[j];
			//printf("%d ",pr[j]);
		}*/
	}
	sort(hh+1,hh+hcnt+1);
	hcnt=unique(hh+1,hh+hcnt+1)-hh-1;
	for(i=1;i<=n;i++)
		for(j=1;j<=cnt[i];j++)
			a[i][j]=lower_bound(hh+1,hh+hcnt+1,a[i][j])-hh;
	for(i=1;i<=95;i++)
		for(j=1;j<=n;j++){
			sum[i][j]+=sum[i][j-1];
			if(sum[i][j]>=mod)sum[i][j]-=mod;
		}
	for(i=1;i<=m;i++){q[i].l=gi();q[i].r=gi();q[i].id=i;if(q[i].l>q[i].r)swap(q[i].l,q[i].r);}
	sort(q+1,q+m+1,cmp);
	
	mul=1;l=1;r=0;
	
	//printf("%.3fs\n",(clock()-c1)/1000);
	//freopen("1.out","w",stdout);
	for(i=1;i<=m;i++){
		while(l>q[i].l){
			l--;
			for(j=1;j<=cnt[l];j++){
				tmp=(++tong[a[l][j]]);
				mul=1ll*mul*inv[tmp]%mod*(tmp+1)%mod;
			}
		}
		while(r<q[i].r){
			r++;
			for(j=1;j<=cnt[r];j++){
				tmp=(++tong[a[r][j]]);
				mul=1ll*mul*inv[tmp]%mod*(tmp+1)%mod;
			}
		}
		while(l<q[i].l){
			for(j=1;j<=cnt[l];j++){
				tmp=(--tong[a[l][j]]);
				mul=1ll*mul*inv[tmp+2]%mod*(tmp+1)%mod;
			}
			l++;
		}
		while(r>q[i].r){
			for(j=1;j<=cnt[r];j++){
				tmp=(--tong[a[r][j]]);
				mul=1ll*mul*inv[tmp+2]%mod*(tmp+1)%mod;
			}
			r--;
		}
		ans[q[i].id]=1ll*mul*query(l,r)%mod;
	}
	for(i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	//freopen("CON","w",stdout);
	//printf("%.3fs\n",(clock()-c1)/1000);
}

 

It should be my PR that has a problem, or PR will be more expensive...

 

 

 

 

 

 

 

 

 

 

128 original articles published, 120 praised, 70000 visitors+
Private letter follow

Tags: less

Posted on Tue, 04 Feb 2020 21:13:09 -0800 by ONiX