玲珑杯 1153 - 无影的神之右手莫队

本文主要是介绍玲珑杯 1153 - 无影的神之右手莫队，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://www.ifrog.cc/acm/problem/1153

1153 - 无影的神之右手

Time Limit：4s Memory Limit：512MByte

Submissions：183Solved：14

DESCRIPTION

觉不觉得这几个图很有毒啊？
其实这几个不算很有毒吧~
由乃懒得写题面了，反正写了也没人看，所以直接说题意吧~
给你一个序列a，每次查询一个区间[l,r]的乘积的约数个数mod 19260817

INPUT

第一行两个数n,m 第二行n个数表示序列a 后面m行每行两个数l,r表示查询区间[l,r]

OUTPUT

对于每个查询输出答案

SAMPLE INPUT

5 5 64 2 18 9 100 1 5 2 4 2 3 1 4 3 4

SAMPLE OUTPUT

165 15 9 45 10

HINT

n , m <= 100000 , a[i] <= 1000000

SOLUTION

“玲珑杯”ACM比赛 Round #20

思路：显然ans利用约数和定理求，约数和定理链接；

　　sqrt（a[i])=1000,

　　对于小于1000的素数，利用前缀和，复杂度m*168（素数总个数）；

　　对于大于1000的素数，一个数最多有一个这样的素数，利用莫队算法，求区间每个数的个数+1的乘积，莫队裸题；复杂度O（m*sqrt（n））；

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define LL long long
const int N=1e5+100,M=1e6+10,inf=1e9+10;
const LL INF=1e18+10,mod=19260817;int inv[M],mp[M];void inverse(int n, int p) {inv[1] = 1;for (int i=2; i<=n; ++i) {inv[i] = (LL) (p - p / i) * inv[p%i] % p;}
}
int pos[N],a[N];
LL out,ans[N];
struct is
{int l,r,now;bool operator < (const is &a)const{if(pos[l]!=pos[a.l])return pos[l]<pos[a.l];return r<a.r;}
} s[N];
void add(int x)
{if(a[x]==1)return;out*=inv[mp[a[x]]+1];out%=mod;mp[a[x]]++;out*=mp[a[x]]+1;out%=mod;
}void del(int x)
{if(a[x]==1)return;out*=inv[mp[a[x]]+1];out%=mod;mp[a[x]]--;out*=mp[a[x]]+1;out%=mod;
}int ssp[N][200],sum[N][200];vector<int>pr;
int vis[N];
void init()
{for(int i=2;i<=1000;i++){if(!vis[i])pr.push_back(i);for(int j=i+i;j<=1000;j+=i)vis[j]=1;}
}
int main()
{inverse(1000000,19260817);init();//cout<<pr.size()<<endl;int n,m;while(~scanf("%d%d",&n,&m)){memset(mp,0,sizeof(mp));out=1;int k=sqrt(n);for(int i=1;i<=n;i++){pos[i]=(i-1)/k+1;scanf("%d",&a[i]);int temp=a[i];for(int j=0;j<pr.size();j++){if(temp%pr[j]==0){while(temp%pr[j]==0){temp/=pr[j];ssp[i][j]++;}}}for(int j=0;j<pr.size();j++)sum[i][j]=sum[i-1][j]+ssp[i][j];a[i]=temp;}for(int i=1;i<=m;i++){scanf("%d%d",&s[i].l,&s[i].r);s[i].now=i;}sort(s+1,s+1+m);int L=1,R=0;for(int i=1; i<=m; i++){while(R>s[i].r){del(R);R--;}while(R<s[i].r){R++;add(R);}while(L<s[i].l){del(L);L++;}while(L>s[i].l){L--;add(L);}LL q=1;for(int j=0;j<pr.size();j++){q*=sum[s[i].r][j]-sum[s[i].l-1][j]+1;q%=mod;}ans[s[i].now]=(out*q)%mod;}for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);}return 0;
}