Codeforces 906 D Power Tower-白红宇

Codeforces 906 D Power Tower

阅读量：5333 次

发布时间：2019-06-15

本文共 2788 字，大约阅读时间需要 9 分钟。

Discription

Priests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the current top of tower and adding rocks at its bottom. If top, which is built from k - 1 rocks, possesses power p and we want to add the rock charged with power w_k then value of power of a new tower will be {

w_k}^p.

Rocks are added from the last to the first. That is for sequence w₁, ..., w_m value of power will be

$\text{[math]}$

After tower is built, its power may be extremely large. But still priests want to get some information about it, namely they want to know a number called cumulative power which is the true value of power taken modulo m. Priests have n rocks numbered from 1 to n. They ask you to calculate which value of cumulative power will the tower possess if they will build it from rocks numbered l, l + 1, ..., r.

Input

First line of input contains two integers n (1 ≤ n ≤ 10⁵) and m (1 ≤ m ≤ 10⁹).

Second line of input contains n integers w_k (1 ≤ w_k ≤ 10⁹) which is the power of rocks that priests have.

Third line of input contains single integer q (1 ≤ q ≤ 10⁵) which is amount of queries from priests to you.

k^th of next q lines contains two integers l_k and r_k (1 ≤ l_k ≤ r_k ≤ n).

Output

Output q integers. k-th of them must be the amount of cumulative power the tower will have if is built from rocks l_k, l_k + 1, ..., r_k.

Example

Input

6 1000000000 1 2 2 3 3 3 8 1 1 1 6 2 2 2 3 2 4 4 4 4 5 4 6

Output

1 1 2 4 256 3 27 597484987

Note

3²⁷ = 7625597484987

首先你得需要知道一个定理：

当x>φ(p)时，a^x mod p=a^(x mod φ(p) +φ(p)) mod p。

因为φ(x)迭代不超过log(x)次就成1了(考虑2这个质因子)，所以我们直接暴力迭代就行了。

由于我们并不知道下一层的值(也就是这一层的次数)是否大于φ(p)，所以%p改成%2p就行了。

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #define ll long long#define maxn 100005using namespace std;ll a[maxn],n,mod[105],l,r,q,tot=0;inline ll MO(ll x,ll y){ return x>y?x%y+y:x;}inline ll ksm(ll x,ll y,const ll ha){ ll an=1; for(;y;y>>=1,x=MO(x*x,ha)) if(y&1) an=MO(an*x,ha); return an;}inline ll phi(ll x){ int tp=sqrt(x+0.5),y=1; for(int i=2;i<=tp;i++) if(!(x%i)){ x/=i,y*=i-1; while(!(x%i)) x/=i,y*=i; if(x==1) break; } if(x!=1) y*=x-1; return y;}ll solve(int now,ll mo){ if(now==r||mo==1) return MO(a[now],mo); else return ksm(a[now],solve(now+1,mod[now-l+1]),mo);}int main(){ scanf("%lld%lld",&n,mod); while(mod[tot]!=1) mod[tot+1]=phi(mod[tot]),tot++; for(int i=1;i<=n;i++) scanf("%lld",a+i); scanf("%lld",&q); while(q--){ scanf("%lld%lld",&l,&r); ll ans=solve(l,mod[0]); if(ans>=mod[0]) ans-=mod[0]; printf("%lld\n",ans); } return 0;}

转载于:https://www.cnblogs.com/JYYHH/p/8384375.html

你可能感兴趣的文章