H.Hamster's Sequence(2019武大校赛现场赛)(莫队or前缀和+离线处理)(吉比特杯第二届湖北省程序设计大赛) 解题报告 Apare_xzc

H.Hamster’s Sequence(2019武大校赛现场赛)(莫队/前缀和+离线处理)(吉比特杯第二届湖北省程序设计大赛) 解题报告

xzc 2019/4/18

CCNU_你们好强啊我们都是面包手

题意：
  给出n个整数a1,a2…an ,和m个询问，每次询问从[L,R]这个区间所有数的乘积的因数的个数 (求a[L]*a[L+1]*a[L+2]*…*a[R-1]*a[R] 的因数的个数)

input:

5 5
1 2 3 4 5
1 1
2 2 
3 3 
1 5
4 5

output:

1
2
2
16
6

分析：
  一个数因数的个数是所有质因子出现的个数+1后的乘积
  剩下的上题解：

• 首先，我们得看出来这道题是个简单题。
• 至于那个合数mod，实际上是唬人的，你一些数乘起来对合数取模可以直接取
• 然后我们根据题目描述我们知道，说ai在2147483647以内，但由ai=rand()*rand()得出，实际上ai的质因子最大的不会超过32767（rand()在c++中的随机数据范围在0到 32767）
• 我们知道一个因数的个数和这个数的质因数的个数有关

A=a1^n1*a2^n2*a3^n3…an^nn因数的个数等于
(1+n1) * (1+n2) * (1+n3) * … * (1+nn)

• 然后计算答案：
  planA: 直接莫队
  planB：对于32767中的质数分别统计对答案的贡献，用前缀和计算即可

先上我的AC代码

/* Author: CCNU XuZhichao state: AC 2019/4/17 22:40 1105 */
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 1e5+20;
const int N = 32767;  //3512个素数
const int mod = 35808247;
int cntOfPrime,sushu[N],n,m;
bool notPrime[N+20];
int mp[N+20];
void getPrime(int &cnt)
{
	cnt = 0;
	For(i,2,N)
	{
		if(!notPrime[i]) mp[i] = cnt, sushu[cnt++] = i;
		for(int j=0;j<cnt&&1ll*i*sushu[j]<=N;++j)
		{
			notPrime[i*sushu[j]] = true;
			if(i%sushu[j]==0) break;
		}
	}
}
pair<int,int> ask[maxn]; 
int a[maxn];
LL ans[maxn];
int sum[maxn];
void f(int i)
{
	int p = sushu[i];
	sum[0] = 0;
	For(i,1,n)
	{
		int x = a[i];
		int cnt = 0;
		while(x%p==0) ++cnt,x/=p;
		sum[i] = sum[i-1]+cnt;
	}
	For(i,1,m)
	{
		int nn = sum[ask[i].second]-sum[ask[i].first-1]+1;
		ans[i] = ans[i]*nn%mod;	
	}
}
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    getPrime(cntOfPrime);
    scanf("%d%d",&n,&m);
    For(i,1,n) scanf("%d",a+i), ans[i] = 1;
    For(i,1,m)
    {
    	scanf("%d%d",&ask[i].first,&ask[i].second);
	}
    For(i,0,3511)
    {
    	f(i);
	}
	For(i,1,m)
		printf("%lld\n",ans[i]);
    
    return 0;
}

这是第一发用vector压缩存储了所有因数前缀和的代码

跑了100多秒，输出都正确，100000(询问)*3512(个素数)*2*log2(100000)(两次二分)

/* Author: CCNU XuZhichao state: TLE 2019/4/17 22:09 1105 */
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 1e5+20;
const int N = 32767;  //3512个素数
const int mod = 35808247;
int cntOfPrime,sushu[N];
bool notPrime[N+20];
int mp[N+20];
void getPrime(int &cnt)
{
	cnt = 0;
	For(i,2,N)
	{
		if(!notPrime[i]) mp[i] = cnt, sushu[cnt++] = i;
		for(int j=0;j<cnt&&1ll*i*sushu[j]<=N;++j)
		{
			notPrime[i*sushu[j]] = true;
			if(i%sushu[j]==0) break;
		}
	}
}
int a[maxn];
vector<pair<int,int> > v[3512];
void f(int id)
{
	int x = a[id],p,t;
	for(int i=0;i<cntOfPrime&&sushu[i]<=x/sushu[i];++i)
	{
		p = sushu[i];
		if(x%p) continue;
		int cntt = 0;
		while(x%p==0) ++cntt,x/=p;
		t = mp[p]; //下标
		int sz = v[t].size();
		if(sz>1) cntt+=v[t][sz-1].second;
		v[t].pb(MP(id,cntt));
	}
	if(x>1)
	{
		t = mp[x];
		int cntt = 1;
		int sz = v[t].size();
		if(sz>1) cntt+=v[t][sz-1].second;
		v[t].pb(MP(id,cntt));
	}
}
int getNum(int L,int R,int i)
{
	int x1 = upper_bound(v[i].begin(),v[i].end(),MP(L,1000))-v[i].begin()-1;
	int x2 = upper_bound(v[i].begin(),v[i].end(),MP(R,1000))-v[i].begin()-1;
	return max(0,v[i][x2].second-v[i][x1].second) + 1;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    getPrime(cntOfPrime);
    For(i,0,3511) v[i].push_back(MP(-2,0));
    int n,m,L,R;
    scanf("%d%d",&n,&m);
    For(i,1,n)
    	scanf("%d",a+i);
    For(i,1,n)
    	f(i); 
    //预处理前缀和0ms 
    while(m--)
    {
    	scanf("%d%d",&L,&R);
    	LL ans = 1;
    	For(i,0,3511) //100000个询问*3000*log(100000); 
    	{
    		ans  = ans * getNum(L-1,R,i)%mod;
		}
		printf("%lld\n",ans);
	}
    return 0;
}

附：武大出题人写的标程(莫队算法)

#include <bits/stdc++.h>
using namespace std;
const int M = 100100;
const long long MOD = 35808247;
//MOD=5981*5987
int n,m;
struct node
{
	int l,r,id;
}q[M];
long long ans[M];
vector<int>b[M];
int hash1[M],block[M];
int num[M],prime[M],len,flag[M];
void update(int x,int y)
{
	for(int i=0;i<b[x].size();i++)
		num[hash1[b[x][i]]]+=y;
}
long long get_ans()
{
	long long cnt=1;
	for(int i=1;i<=len;i++)
		if(num[i]!=0)
			cnt=cnt*(num[i]+1)%MOD;
	return cnt; 
}
bool cmp(const node &x,const node &y)
{
	if(block[x.l]==block[y.l])
		return x.r<y.r;
	return x.l<y.l;
}
void deal()
{
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		for(;r<q[i].r;r++)
			update(r+1,1);
		for(;r>q[i].r;r--)
			update(r,-1);
		for(;l<q[i].l;l++)
			update(l,-1);
		for(;l>q[i].l;l--)
			update(l-1,1);
		ans[q[i].id]=get_ans();
	}
}
void print()
{
	for(int i=1;i<=m;i++)
		printf("%I64d\n",ans[i]);
	printf("\n");
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("stdout.txt","w",stdout); 
	for(int i=2;i<=40000;i++)
		if(!flag[i])
		{
			prime[++len]=i;
			for(int j=i*i;j<=40000;j+=i)
				flag[j]=1;
			hash1[i]=len;
		}
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		for(int j=1;prime[j]*prime[j]<=x;j++)
			while(x%prime[j]==0)
			{
				b[i].push_back(prime[j]);
				x/=prime[j];
			}
		if(x!=1)
			b[i].push_back(x);
	}
	int block_num=300;
	for(int i=1;i<=n;i++)
		block[i]=(i/block_num)+(i%block_num==0);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+1+n,cmp);
	deal();
	print();
	return 0;
} 

2019/4/18 07:11