关于卡常。
查看原帖
关于卡常。
97582
星夜之使楼主2021/1/22 10:52

怎么说......交了五页了orz，整体来说时间快了0.7s.....不过最后一个点是什么极限数据莫（楞，总之就是过不去orz.....

以下代码

#include<bits/stdc++.h>
#define IT unordered_set<int>::iterator
using namespace std;

inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)? EOF : *p1++;
}

inline long long q_read()
{
    char c=nc();
	long long num=0;
	
    while(c<'0'||c>'9')
	{
		c=nc();
	}
	
    while(c>='0'&&c<='9')
	{
		num*=10;
		num+=c-'0';
		c=nc();
	}
	
    return num;
}

const int MAXN=100000+10,mod=19260817;

int n,m,ls,kuai,cnt=0,suc=0;
unordered_map<int,int> check2,ys;

int flag[MAXN*100]={0},prime[MAXN*10];

void init2()
{
	for(register int i=2;i<=100000;i++) 
	{
		if(!flag[i])
			prime[++suc] = i,flag[i]=1;
		
		for(int j=1;j<=suc&&i*prime[j]<=100000;j++) 
		{
			flag[i*prime[j]]=2;
			if(i%prime[j]==0) break;
		}
	}
}

struct query
{
	int l,r,pl,num;
	
	bool operator < (const query b) const
	{
		if(pl^b.pl) return pl<b.pl;
		else if(pl&1) return r>b.r;
		else return r<b.r;
	}
} q[MAXN];

int val[MAXN],su[MAXN],ni[MAXN*2];
int l2s[MAXN*2],uu=0,buc[MAXN*2];

void get_inv(int num)
{
	ni[1]=1;
	
	for(register int i=2;i<=num;i++)
	{
		ni[i]=(long long)(mod-mod/i)*ni[mod%i]%mod;
	}
}

inline int mul(long long a,long long b,int mod)
{
	int tmp=a*b-(long long)((long double)a*b/mod+0.5)*mod;
	return tmp<0 ? tmp+mod :tmp;
}

inline int ksm(int a,int b,int mod)
{
	int ret=1;
	
	while(b)
	{
		if(b&1) ret=mul(ret,a,mod);
		
		b>>=1;
		a=mul(a,a,mod);
	}
	
	return ret;
}

inline int gcd(int a,int b)
{
	if(!b) return a;
	return gcd(b,a%b);
}

inline int if_prime(int x,int num)
{
	int tmp=num-1,tmp2=0;
	
	while(!(tmp&1))
	{
		tmp>>=1;
		tmp2++;
	}
	
	int ret=ksm(x,tmp,num);
	
	if((!(ret^1))||(!(ret^(num-1)))) return 0;
	
	while(tmp2--)
	{
		ret=mul(ret,ret,num);
		
		if(!(ret^(num-1))) return 0;
	}
	
	return 1;
}

unordered_set<int> check;

inline void init()
{
	check.insert(2),check.insert(3),check.insert(5);
	check.insert(7),check.insert(61),check.insert(24251);
//	check.insert(11),check.insert(13),check.insert(10007);
//	check.insert(rand()%30000+1000),check.insert(rand()%30000+1000);
}

int miller_rabin(int x)
{
	if(x==2||x==3||x==5||x==7||x==61||x==24251||x==11||x==13||(x<=100000&&flag[x]==1)) return 1;
	if(x%2==0||x<2) return 0;
	
//	cout<<1<<endl;
//	exit(0);
	
/*	for(IT it=check.begin();it!=check.end();it++)
	{
	//	cout<<x<<" "<<(*it)<<endl;
		if(!(x%(*it))) return 0;
	}*/
	
	for(IT it=check.begin();it!=check.end();it++)
	{
		if(if_prime(*it,x)) return 0;
	}
	
	return 1;
}

inline int pollard_rho(int x)
{
	int s=0,t=0;
	int c=rand()%(x-1)+1;
	
	for(int goal=2,val=1; ;goal<<=1,s=t,val=1)
	{
		for(int step=1;step<=goal;step++)
		{
			t=(mul(t,t,x)+c)%x;
			val=mul(val,abs(t-s),x);
			
			if(!(step&63))
			{
				int tmp=gcd(val,x);
				if(tmp>1) return tmp;
			}
		}
		
		int tmp=gcd(val,x);
		if(tmp>1) return tmp;
	}
}

int use=1;

void fac(int x)
{
	if(x<=use||x<=1000) return ;
	
//	cout<<x<<endl;
	
	if(miller_rabin(x))
	{
		use=x;
		return ;
	}
	
	int p=x;
	
	while(p>=x) p=pollard_rho(x);
	while(!(x%p)) x/=p;
	
	fac(x);
	
	if(use^1) return ;
	
	fac(p);
	
	if(use^1) return ;
}


int qzh[MAXN][170]={0};
int su1[MAXN][3]={0},su1_num[MAXN]={0};
int l=1,r=0;

int sav=1,ans[MAXN],out=1;

int main()
{

	ios::sync_with_stdio(0);

	srand(19260817);

	init();
	init2();

	n=q_read();
	m=q_read();
	
	get_inv(2*n+10);
	
	for(register int i=2;i<=1000;i++)
	{
		if(flag[i]==1) su[++cnt]=i;
	}
	
	for(register int i=1;i<=n;i++)
	{
		val[i]=q_read();
	}
	
	for(int i=1;i<=n;i++)
	{
		for(register int j=1;j<=cnt;j++)
		{
		//	cout<<su[j]<<" ";
		
			qzh[i][j]=qzh[i-1][j];
			
			while(!(val[i]%su[j])) qzh[i][j]++,val[i]/=su[j];
		}
		
		if(val[i]==1) continue ;
		
		use=1;
		
		fac(val[i]);
		
		if(use!=1&&!check2[use]) l2s[++uu]=use,check2[use]=1;
		
		if(use^1) su1[i][++su1_num[i]]=use;
		
		if(val[i]/use!=1&&!check2[val[i]/use]) l2s[++uu]=val[i]/use,check2[val[i]/use]=1;
	
		if(val[i]/use!=1) su1[i][++su1_num[i]]=val[i]/use;
	}
	
//	return 0;
	
//	cout<<uu<<endl;
	
	sort(l2s+1,l2s+uu+1);
	
	for(register int i=1;i<=uu;i++)
	{
		ys[l2s[i]]=i;
	}
	
	for(register int i=1;i<=n;i++)
		for(register int j=1;j<=su1_num[i];j++)
			su1[i][j]=ys[su1[i][j]];
			
/*	for(int i=1;i<=n;i++,cout<<endl)
		for(int j=1;j<=su1_num[i];j++)
			cout<<su1[i][j]<<" ";*/
		
	kuai=sqrt(m)+1;
	
	for(register int i=1;i<=m;i++)
	{
		q[i].l=q_read(),q[i].r=q_read();
		q[i].pl=q[i].l/kuai;
		q[i].num=i;	
	}
	
	sort(q+1,q+m+1);
	
	for(int i=1;i<=m;i++)
	{
		int tmp;
	
		while(l>q[i].l)
		{
		//	cout<<l<<" ";
		
			l--;
			
			if(!(val[l]^1)) continue;
			
			tmp=su1[l][1];
			
		//	cout<<l<<" "<<tmp<<endl;
			
			if(tmp) (++buc[tmp])-1 ? out=mul(mul(out,ni[buc[tmp]],mod),buc[tmp]+1,mod) : out=mul(out,buc[tmp]+1,mod);
			if(su1_num[l]==2) tmp=su1[l][2],(++buc[tmp])-1 ? out=mul(mul(out,ni[buc[tmp]],mod),buc[tmp]+1,mod) : out=mul(out,buc[tmp]+1,mod);
		}
		
		while(r<q[i].r)
		{
		//	cout<<r<<endl;
		
			r++;
			
			if(!(val[r]^1)) continue;
			
			tmp=su1[r][1];

			
		//	cout<<r<<" "<<tmp<<endl;;
			
			if(tmp) (++buc[tmp])-1 ? out=mul(mul(out,ni[buc[tmp]],mod),buc[tmp]+1,mod) : out=mul(out,buc[tmp]+1,mod);
			
		//	cout<<buc[tmp]<<" "<<out<<endl;
			
			if(su1_num[r]==2) tmp=su1[r][2],(++buc[tmp])-1 ? out=mul(mul(out,ni[buc[tmp]],mod),buc[tmp]+1,mod) : out=mul(out,buc[tmp]+1,mod);
			
		//	cout<<out<<endl;
		}
		
		while(l<q[i].l)
		{		

		
			if(!(val[l]^1)) goto ed;	
			
			tmp=su1[l][1];
		//	cout<<l<<" "<<tmp<<endl;;

			if(tmp) (--buc[tmp]) ? out=mul(mul(out,ni[buc[tmp]+2],mod),buc[tmp]+1,mod) : out=mul(out,ni[buc[tmp]+2],mod);
			if(su1_num[l]==2) tmp=su1[l][2],(--buc[tmp]) ? out=mul(mul(out,ni[buc[tmp]+2],mod),buc[tmp]+1,mod) : out=mul(out,ni[buc[tmp]+2],mod);
			
			ed:
			
			l++;
		}
		
		while(r>q[i].r)
		{		
			if(!(val[r]^1)) goto ed2;
		
			tmp=su1[r][1];
		//	cout<<r<<" "<<tmp<<endl;;

			if(tmp) (--buc[tmp]) ? out=mul(mul(out,ni[buc[tmp]+2],mod),buc[tmp]+1,mod) : out=mul(out,ni[buc[tmp]+2],mod);
			if(su1_num[r]==2) tmp=su1[r][2],(--buc[tmp]) ? out=mul(mul(out,ni[buc[tmp]+2],mod),buc[tmp]+1,mod) : out=mul(out,ni[buc[tmp]+2],mod);
			
			ed2:
			
			r--;
		}
		
		ans[q[i].num]=out;
	//	cout<<out<<endl;
		
		for(int j=1;j<=cnt;j++)
		{
			ans[q[i].num]=mul(ans[q[i].num],qzh[q[i].r][j]-qzh[q[i].l-1][j]+1,mod);
		}
	}	
	
	for(register int i=1;i<=m;i++)
	{
		cout<<ans[i]<<endl;
	}
	
	return 0;
}
2021/1/22 10:52