codeforces 594 D. REQ (树状数组+欧拉函数+逆元)
题意：给出n个数,q个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+7的答案是多少。
思路：这道题需要一点欧拉函数的知识。
phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。
To calculate the answer on every query let's use the formula
, where _p_1, p_2, ..., p__k — all prime numbers which divided_n.
如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。
考虑两个数a,b的欧拉函数。
一开始考虑也许有什么性质。。。查了下欧拉函数的wiki 欧拉函数_维基百科 欧拉函数是积性函数（但不是完全积性函数。。因此必须phi(ab) =phi(a)*phi(b)成立当且仅当gcd(a,b)==1)
然而这里并不一定满足互质的条件。。。
再想一下。。。发现完全没必要由phi(a)和phi(b)得到phi(a*b)
直接把a*b看成一个数就好了。。。。
后面质因子乘积部分只需要把两部分的并在一起就好了。。。
所以根据上面欧拉函数的公式。。。答案分为两部分。。。
一部分是区间中所有数的乘积。。。
一部分是区间中所有数的不相同的素因子的p-1/p形式的乘积。。。
第一部分预处理前缀积即可。。。由于有%运算。。。所以除的时候需要计算逆元。。。
第二部分的做法同spoj_dquery解题报告
也是离线处理，把询问按照区间右端点排序升序排列，然后lst数组记录上次该数出现的位置。。。用bit维护一个从1到某个数的乘积。。。在撤销的时候同样需要逆元。。。
还要注意。。。太长的式子一定要分开写。。。。
因为写错括号顺序调了半天orz...
1/* ***********************************************
2Author :111qqz
3Created Time :Thu 22 Sep 2016 02:07:39 PM CST
4File Name :code/cf/problem/594D.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=2E5+7;
32const int M=1E6+7;
33const LL MOD = 1E9+7;
34struct node
35{
36 int l,r;
37 int id;
38 bool operator < (node b)const
39 {
40 return r<b.r;
41 }
42}q[N];
43LL a[N],pre[N];
44int lst[M];
45int n,Q;
46LL ksm(LL a,LL b)
47{
48 LL res = 1LL;
49 while (b>0LL)
50 {
51 if (b%2)
52 res = (res*a)%MOD;
53 b = b>>1LL;
54 a = (a*a)%MOD;
55 }
56 return res;
57}
58LL get_inv(LL x){
59 return ksm(x,MOD-2);
60}
61bool vis[M];
62vector <int>factor[M];
63void init( ) //预处理1到1E6的每个数的质因子
64{
65 ms(vis,false);
66 for ( int i = 2 ; i < M ; i++)
67 if (!vis[i])
68 for ( int j = i ; j < M ; j+=i)
69 vis[j] = true,factor[j].push_back(i);
70}
71LL t[M];
72int lowbit( int x)
73{
74 return x&(-x);
75}
76void update( int x,LL delta)
77{
78 for ( int i = x ; i <= n ; i+=lowbit(i) )
79 t[i] = (t[i] * delta)%MOD;
80}
81LL get_mul( int x)
82{
83 LL res = 1LL;
84 for ( int i = x ; i >= 1 ; i-=lowbit(i))
85 res = (res * t[i])%MOD;
86 return res;
87}
88LL ans[N];
89int main()
90{
91 #ifndef ONLINE_JUDGE
92 freopen("code/in.txt","r",stdin);
93 #endif
94 init();
95 ms(lst,0);
96 scanf("%d",&n);
97 for ( int i = 1 ; i < M ; i++) t[i] = 1LL; //bit的初始化。。由于是乘积。。所以初始化为1.
98 pre[0]=1LL;
99 for ( int i = 1 ; i <= n ; i++) scanf("%lld",a+i),pre[i] = (pre[i-1]*a[i])%MOD;
100 scanf("%d",&Q);
101 for ( int i = 1 ; i <= Q ; i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
102 sort(q+1,q+Q+1);
103 int cur = 1;
104 for ( int i = 1 ; i <= Q ; i++)
105 {
106 for ( ; cur <= q[i].r ; cur++)
107 {
108 int siz = factor[a[cur]].size();
109 for ( int j = 0 ; j < siz; j++)
110 {
111 int val = factor[a[cur]][j];
112 if (lst[val])
113 {
114 update(lst[val],val);
115 update(lst[val],get_inv(val-1));
116 }
117 update(cur,val-1);
118 update(cur,get_inv(val));
119 lst[val] = cur;
120 }
121 }
122 LL ans1 = get_mul(q[i].r)*get_inv(get_mul(q[i].l-1))%MOD;
123 LL ans2 = pre[q[i].r]*get_inv(pre[q[i].l-1])%MOD;
124 ans[q[i].id] = (ans1*ans2)%MOD;
125 //mgj....这种这么长的一堆括号的式子分开写会死啊。。。。。。有毒。
126 //ans[q[i].id] = (( get_mul(q[i].r)*get_inv(get_mul(q[i].l-1))%MOD ) * ( pre[q[i].r] * get_inv( pre[q[i].l-1] )%MOD ) )%MOD;
127 }
128 for ( int i = 1 ; i <= Q ; i ++) printf("%lld\n",ans[i]);
129 #ifndef ONLINE_JUDGE
130 fclose(stdin);
131 #endif
132 return 0;
133}