题目：http://acm.nuc.edu.cn/OJ/contest/show/54/1008

SHT作为实验室的第一帅哥，一直有一个梦想，希望自己不要长得这么帅，长得帅的苦恼实在是太多了。为了让自己变得没那么帅，他开始疯狂的熬夜刷题，希望通过这样的方式让自己有黑眼圈，然侯实现没那么帅的梦想。终于在一个阳光明媚的下午，SHT终于熬不住了，他想睡觉，非常的想睡觉，此时的他也终于实现了黑眼圈的梦想。于是实验室的伙伴们准备把他抬回宿舍好好休息，他实在是太累了。可是他却拒绝了我们的帮助，坚持说：“不行~~~我一定要把这题做出来再睡~~~。”实验室的伙伴们都为他坚持不懈的精神而动容，纷纷投去崇拜的目光，没想到SHT学长不仅长得帅，竟然还有这么高尚的品格，实在是完美的男生啊。这时WYS也被他的精神所打动，作为实验室的最强者，他决定要帮助SHT，于是他将目光投向了SHT的屏幕。

给一个长为n的序列，进行 m 次操作，一共有两种操作：

1.区间 [l, r] 的每个数加上 x 。

2.对于区间 [l, r]，查询a[l]a[l+1]a[l+2].....mod p，一直到 a[r] 。

请注意每次的模数p不同。

请输出每次操作2查询的值。

强大的WYS很快就写出了答案，在SHT被抬走的最后一刻，WYS拍了拍SHT的肩膀语重心长的说：“SHT啊，除了刷题外一定还要加强锻炼，要文体两开花，两开花啊！”

 

输入描述

第一行两个整数 n,m 表示序列长度和操作数


接下来一行，n个整数，表示这个序列


接下来m行，可能是以下两种操作之一：


操作1：区间 [l, r] 的每个数加上 x 。

 

操作2：对于区间 [l, r]，查询a[l]a[l+1]a[l+2].....mod p，一直到 a[r] 。

 

1 <= n, m <= 500000

1 <= l <= r <= n

1 <= x <= 2e9

1 <= p <= 2e7

输出描述

对于每个询问，输出一个数表示答案

样例输入

6 4
1 2 3 4 5 6
2 1 2 10000007
2 2 3 5
1 1 4 1
2 2 4 10

样例输出

1
3
1

欧拉定理 + 树状数组

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
const int maxn = 100 * 1000 * 5 + 10;
const int maxm = 2 * 1e7 + 10;
ll n,m;
ll phi[maxm],a[maxn];


struct BIT{
	ll s[maxn];
	BIT() {
		memset(s,0,sizeof(s));
	}

	ll lowerbit(ll x) { return x & -x; }

	void add(ll x, ll v) {
		while (x <= n)s[x] += v, x += lowerbit(x);
	}

	ll query(int x) {
		ll ans = 0;
		while (x)ans += s[x], x -= lowerbit(x);
		return ans;
	}
}bit;

void Eul_list() {
	memset(phi,0,sizeof(phi));
	phi[1] = 1;
	for (int i = 2; i < maxm; i++) {
		if(!phi[i])
			for (int j = i; j < maxm; j += i) {
				if (!phi[j])phi[j] = j;
				phi[j] = phi[j] / i * (i - 1);
			}
	}
}

ll Mod(ll x, ll p) {
	return x < p ? x : x % p + p;
}

ll quik(ll x, ll n, ll p) {
	ll ans = 1;
	while (n) {
		if (n & 1)ans = ans * x%p;
		x = x * x%p;
		n >>= 1;
	}
	return ans;
}
ll  solve(ll L, ll R, ll p) {
	ll a = bit.query(L);
	if (L == R || p == 1)return Mod(a,p);
	return quik(a, solve(L + 1, R, phi[p]), p);
}

int main() {
	Eul_list();
	scanf("%lld%lld",&n,&m);
	for (int i = 1; i <= n; i++)scanf("%lld",a+i),bit.add(i,a[i]-a[i-1]);

	ll op, L, R, x;
	while (m--) {
		scanf("%lld%lld%lld%lld",&op,&L,&R,&x);
		if (op == 1) {
			bit.add(L,x);
			bit.add(R+1,-x);
		}
		else {
			printf("%lld\n",solve(L,R,x));
		}
	}

	return 0;

}