题目链接：http://codeforces.com/contest/906/problem/D
题意：
给你n个数，再给你l~r，求
%m
题解：
一开始不会
后来查到了欧拉降幂定理：
然后就会了
这样的话，每次从左往右求ans就变成了不断求n^x%m,依次往右递归即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
int i,j,k,n,x,y,t,q;
ll a[N],m;
map <ll,ll> f;
ll jisuan(ll n){
if (f.count(n))return f[n];
ll ans = n, z = n;for (ll i = ; i * i <= n; ++i){if (n % i == ){ans -= ans / i;while (n % i == ) n /= i;}}
if (n > ) ans -= ans / n;return f[z] = ans;
}
ll Pow(ll a,ll b,ll mod){
ll ret = ;ll fl = a >= mod;
for (; b; b >>= ){if (b & ){ret *= a;if (ret >= mod) fl = , ret %= mod;}a *= a;if (a >= mod) a %= mod, fl = ;}
return ret + fl * mod;
}
ll solve(int l, int r,ll mod){if (l == r) return a[l];if (mod == ) return ;return Pow(a[l], solve(l + , r, jisuan(mod)), mod);}
int main(){
scanf("%d%lld",&n,&m);
for (int i=;i<=n;++i)scanf("%lld",&a[i]);
scanf("%d",&q);
while (q--){scanf("%d%d",&x,&y);printf("%lld\n",solve(x, y, m)%m);}
return ;
}