欧拉降幂
题目: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;
}