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...

/* ***********************************************
Author :111qqz
Created Time :Thu 22 Sep 2016 02:07:39 PM CST
File Name :code/cf/problem/594D.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=2E5+7;
const int M=1E6+7;
const LL MOD = 1E9+7;
struct node
{
    int l,r;
    int id;
    bool operator < (node b)const
    {
	return r<b.r;
    }
}q[N];
LL a[N],pre[N];
int lst[M];
int n,Q;
LL ksm(LL a,LL b)
{
    LL res = 1LL;
    while (b>0LL)
    {
	if (b%2)
	    res = (res*a)%MOD;
	b = b>>1LL;
	a = (a*a)%MOD;
    }
    return res;
}
LL get_inv(LL x){
    return ksm(x,MOD-2);
}
bool vis[M];
vector <int>factor[M];
void init( ) //预处理1到1E6的每个数的质因子
{
    ms(vis,false);
    for ( int i = 2 ; i < M ; i++) 
	if (!vis[i])
	    for ( int j = i ; j < M ; j+=i)
		vis[j] = true,factor[j].push_back(i);
}
LL t[M];
int lowbit( int x) 
{
    return x&(-x);
}
void update( int x,LL delta)
{
    for ( int i = x ; i <= n ; i+=lowbit(i) )
	t[i] = (t[i] * delta)%MOD;
}
LL get_mul( int x)
{
    LL res = 1LL;
    for ( int i = x ; i >= 1 ; i-=lowbit(i))
	res = (res * t[i])%MOD;
    return res;
}
LL ans[N];
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	init();
	ms(lst,0);
	scanf("%d",&n);
	for ( int i = 1 ;  i < M ; i++) t[i] = 1LL; //bit的初始化。。由于是乘积。。所以初始化为1.
	pre[0]=1LL;
	for ( int i = 1 ; i <= n ; i++) scanf("%lld",a+i),pre[i] = (pre[i-1]*a[i])%MOD;
	scanf("%d",&Q);
	for ( int i = 1 ; i <= Q ; i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
	sort(q+1,q+Q+1);
	int cur = 1;
	for ( int i = 1 ; i <= Q ; i++)
	{
	    for  ( ; cur <= q[i].r ; cur++)
	    {
		int siz = factor[a[cur]].size();
		for ( int j = 0 ; j < siz;  j++)
		{
		    int val = factor[a[cur]][j];
		    if (lst[val])
		    {
			update(lst[val],val);
			update(lst[val],get_inv(val-1));
		    }
		    update(cur,val-1);
		    update(cur,get_inv(val));
		    lst[val] = cur;
		}
	    }
	    LL ans1 = get_mul(q[i].r)*get_inv(get_mul(q[i].l-1))%MOD;
	    LL ans2 = pre[q[i].r]*get_inv(pre[q[i].l-1])%MOD;
	    ans[q[i].id] = (ans1*ans2)%MOD;
	    //mgj....这种这么长的一堆括号的式子分开写会死啊。。。。。。有毒。
	    //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;
	}
	for ( int i = 1 ; i <= Q ; i ++) printf("%lld\n",ans[i]);
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}