dC Loves Number Theory
题目大意：dC 在秒了BZOJ 上所有的数论题后，感觉萌萌哒，想出了这么一道水题，来拯救日益枯竭的水题资源。 给定一个长度为 n的正整数序列A，有q次询问，每次询问一段区间内所有元素乘积的φ（φ(n)代表1~n 中与n互质的数的个数） 。由于答案可能很大，所以请对答案 mod 10^6 + 777。 （本题强制在线，所有询问操作的l,r都需要 xor上一次询问的答案 lastans，初始时，lastans = 0）
数据范围：1<=N<=50000，1<=Q<=100000，1<=Ai<=10^6。
题解：
完全不会.....
听了$lijinnn$讲了才明白。
有一个非常非常重要的性质，如果没发现的话根本做不了。
我们考虑暴力怎么搞：每次全扫一遍，然后统计答案。
这也太暴力了....我们优化优化。
这样，每个位置开一个长度最多为$7$的数组表示当前位置的质因子因为我们知道：
$\varphi(n) = n*\prod\limits_{p_i|n} \frac{p_i - 1}{p_i}$。
这复杂度是$O(n^2\times 7)$的。
再优化优化？？？
发现，对于每个左端点，我可以维护处每个质因子在当前左端点右边最靠左出现的位置。
就是先扫一遍整个数组，先求出来左端点在$1$时，每个质数最左出现的位置。
接着每次，左端点往右动，更新当前左端点所在位置的值的所有质因子的答案即可，这样再查询就是在左端点对应的数组上查就好了，这是$O(n)$的。
好，现在的复杂度到了$O(n^2)$，重点就是维护每个质因子在不超过左端点的情况下，最左的位置。
那正解不就出来了么！
我们发现，左端点每动一次，更改的值只有最多$7$个，剩下的值都是相同的。
什么东西可以维护这个？就是一大堆都一样，只有几个不同
主席树呀，我们对每个左端点开一棵主席树，直接维护刚才说的数组。
咋维护呢？
就是对于第$i$颗主席树，如果有一个质数$p$在$i$左侧最左的位置是$j$，那就在主席树$j$的位置$*=\frac{p - 1}{p}$，然后主席树节点维护所支配区间所有数乘积。
但是，每个点单独质因数分解是$O(n\sqrt{a_i})$的，我们通过预处理质数，然后枚举质数的方式就好啦，复杂度是调和级数$O(nln\ n)$。
主席树的复杂度是$O(nlogn)$，每次$O(loglogn)$次，总复杂度是$O(nlognloglogn + nln\ n)$。
代码：
#include <bits/stdc++.h>
#define N 50010
using namespace std;
const int mod = 1000777 ;
typedef long long ll;
vector <int> v[1000010 ];
int prime[1000010 ], cnt;
bool vis[1000010 ];
int pre[1000010 ], bfr[N], a[N];
int ls[N * 200], rs[N * 200], sum[N * 200], root[N * 200], tot;
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
int qpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = (ll)ans * x % mod;
y >>= 1;
x = (ll)x * x % mod;
}
return ans;
}
void init() {
for (int i = 2; i <= 1000000; i ++ ) {
if (!vis[i])
prime[ ++ cnt] = i;
for (int j = 1; j <= cnt && (ll)i * prime[j] <= 1000000; j ++ ) {
vis[i * prime[j]] = true;
if (i % prime[j] == 0) {
break;
}
}
}
}
void update(int x, int val, int l, int r, int pre, int &p) {
p = ++tot;
ls[p] = ls[pre];
rs[p] = rs[pre];
sum[p] = (ll)sum[pre] * val % mod;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
update(x, val, l, mid, ls[pre], ls[p]);
else
update(x, val, mid + 1, r, rs[pre], rs[p]);
}
int query(int x, int y, int l, int r, int p) {
if (!p) {
return 1;
}
if (x <= l && r <= y) {
return sum[p];
}
int ans = 1, mid = (l + r) >> 1;
if (x <= mid)
ans = (ll)ans * query(x, y, l, mid, ls[p]) % mod;
if (mid < y)
ans = (ll)ans * query(x, y, mid + 1, r, rs[p]) % mod;
return ans;
}
int main() {
int n = rd(), m = rd();
for (int i = 1; i <= n; i ++ ) {
a[i] = rd();
}
bfr[0] = 1;
for (int i = 1; i <= n; i ++ ) {
bfr[i] = (ll)bfr[i - 1] * a[i] % mod;
}
init();
for (int i = 1; i <= cnt; i ++ ) {
for (int j = prime[i]; j <= 1000000; j += prime[i]) {
v[j].push_back(i);
}
}
// cout << prime[cnt] << endl ;
// for (int i = 1; i <= n; i ++ ) {
// int len = v[a[i]].size();
// for (int j = 0; j < len; j ++ ) {
// printf("%d ",prime[v[a[i]][j]]);
// }
// puts("");
// }
sum[0] = 1;
for (int i = 1; i <= n; i ++ ) {
int len = v[a[i]].size();
for (int j = 0; j < len; j ++ ) {
if (pre[v[a[i]][j]]) {
update(pre[v[a[i]][j]], (ll)prime[v[a[i]][j]] * qpow(prime[v[a[i]][j]] - 1, mod - 2) % mod, 1, n, (root[i] ? root[i] : root[i - 1]), root[i]);
}
update(i, (ll)(prime[v[a[i]][j]] - 1) * qpow(prime[v[a[i]][j]], mod - 2) % mod, 1, n, (root[i] ? root[i] : root[i - 1]), root[i]);
// printf("Shit %d\n",v[a[i]][j]);
pre[v[a[i]][j]] = i;
}
}
// cout << sum[root[1]] << endl ;
// cout << (ll)sum[root[1]] * 3 % mod * qpow(2, mod - 2) % mod << endl ;
// cout << sum[root[4]] << endl ;
// cout << (ll)sum[root[4]] * 2 * 6 * 4 % mod * qpow(3, mod - 2) % mod * qpow(2, mod - 2) % mod * qpow(5, mod - 2) % mod * qpow(7, mod - 2) % mod << endl ;
// puts("Fuck");
int lastans = 0;
for (int i = 1; i <= m; i ++ ) {
int x = rd(), y = rd();
x ^= lastans, y ^= lastans;
if (x > y) {
lastans = 1;
puts("0");
continue;
}
// cout << (ll)bfr[y] * qpow(bfr[x - 1], mod - 2) % mod << endl ;
lastans = (ll)bfr[y] * qpow(bfr[x - 1], mod - 2) % mod * query(x, y, 1, n, root[y]) % mod;
printf("%d\n", lastans);
}
return 0;
}
小结：真的是好题啊，重要的是那个性质能不能发现。主席树的运用也非常巧妙。