1153 - 无影的神之右手(莫队算法)

“玲珑杯”ACM比赛 Round #20

解题思路：我们首先对每个数进行素数分解，大于1000的因子最多只有一个，小于1000的因子我们暴力记录，然后对于大于1000的因子用莫队处理就好。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
using namespace std;
typedef long long LL;
inline bool scan_d(int &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;
}
const int maxn = 100000 + 10;
const LL mod = 19260817;
int n, m;
LL s0;
int num[1000005];
int a[maxn];
int b[maxn];//大于1000的质因子
LL term[maxn];
int L, R;
bool valid[10005];
int prime[10005];
int dp[maxn][200];//dp[i][j]前i个数,质因子为primep[j]的个数
int inv[100005];
int pos[maxn];
int tot;
int judge;
int block;
struct query
{int l, r;int id;int loc;bool operator <(const query &res) const{if(loc == res.loc) return r < res.r;else return loc < res.loc;}}Query[maxn];
LL quick_pow(LL x, LL i)
{LL ans = 1;x %= mod;if(x == 1) return 1;while(i){if(i&1) ans = (ans * x) % mod;i >>= 1;x = (x * x) % mod;}return ans;
}
void getPrime()
{memset(valid, true, sizeof(valid));tot = 0;for(int i = 2; i <= 10000; i++){if(valid[i]){prime[++tot] = i;}for(int j = 1; j <= tot && prime[j] * i <= 10000; j++){valid[i * prime[j]] = false;if(i % prime[j] == 0) break;}}for(int i = 1; i <= tot; i++){if(prime[i] > 1000){judge = i - 1;break;}}for(int i = 1; i < 100004; i++){inv[i] = (int)quick_pow((LL)i, mod - 2);}
}
void init()
{L = 1;R = 1;memset(num, 0, sizeof(num));memset(dp, 0, sizeof(dp));memset(b, 0, sizeof(b));block = sqrt(n);s0 = 1;
}
void add(int x)
{LL temp = (LL)inv[num[x] + 1];s0 = (s0 * temp) % mod;num[x]++;s0 = (s0 * (num[x] + 1)) % mod;}
void sub(int x)
{LL temp = (LL)inv[num[x] + 1];s0 = (s0 * temp) % mod;num[x]--;s0 = (s0 * (num[x] + 1)) % mod;
}
int main()
{//freopen("C:\\Users\\creator\\Desktop\\A2.in","r",stdin) ;//freopen("C:\\Users\\creator\\Desktop\\out.txt","w",stdout) ;getPrime();//cout<<"judge == "<<judge<<endl;while(~scanf("%d%d", &n, &m)){//printf("n == %d m == %d\n", n, m);init();for(int i = 1; i <= n; i++){//scanf("%d", &a[i]);scan_d(a[i]);pos[i] = i / block;}for(int i = 1; i <= n; i++){for(int j = 1; j <= judge; j++){int temp = 0;while(a[i] % prime[j] == 0){temp++;a[i] /= prime[j];}dp[i][j] = dp[i - 1][j] + temp;}if(a[i] != 1) b[i] = a[i];}for(int i = 1; i <= m; i++){//scanf("%d%d", &Query[i].l, &Query[i].r);scan_d(Query[i].l);scan_d(Query[i].r);Query[i].id = i;Query[i].loc = pos[Query[i].l];}sort(Query + 1, Query + m + 1);if(b[1] != 0) add(b[1]);for(int i = 1; i <= m; i++){int l = Query[i].l;int r = Query[i].r;while(R < r){R++;if(b[R]){add(b[R]);}}while(L > l){L--;if(b[L]){add(b[L]);}}while(L < l){if(b[L]){sub(b[L]);}L++;}while(R > r){if(b[R]){sub(b[R]);}R--;}LL re = 1;for(int j = 1; j <= judge; j++){LL d = (LL)(dp[r][j] - dp[l - 1][j]);if(d) re = (re * (d + 1)) % mod;}re = (re * s0) % mod;term[Query[i].id] = re;}for(int i = 1; i <= m; i++){printf("%lld\n", term[i]);}}return 0;
}