首页 > 代码库 > bzoj4869
bzoj4869
http://www.lydsy.com/JudgeOnline/problem.php?id=4869
终于A了。。。参考了下dalao的代码。。。
拓展欧几里得定理,改了几次就不变了,但是用的时候要在快速幂里判是不是要用。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100010; int n, m, cnt; ll p, c; ll phi[N], table[N]; namespace seg // n^x = n^(x % phi[x] + phi[x]) { struct data { ll ans, mn; } tree[N << 2]; inline ll getphi(ll x) { ll ret = x, lim = x; for(ll i = 2; i * i <= lim; ++i) if(x % i == 0) { ret = ret * (i - 1) / i; while(x % i == 0) x /= i; } // printf("ret=%d\n", ret); if(x > 1) ret = ret * (x - 1) / x; return ret; } inline ll power(ll x, ll t, ll p, bool &flag) { bool big = false; ll ret = 1; for(; t; t >>= 1) { if(t & 1) { ret = ret * x ; flag |= big | (ret >= p); ret %= p; } x = x * x; if(x >= p) big = true, x %= p; } return ret; } ll calc(ll x, int t) { if(x >= phi[t]) x = x % phi[t] + phi[t]; for(int i = t - 1; i >= 0; --i) { bool flag = false; x = power(c, x, phi[i], flag); if(flag) x += phi[i]; } return x % phi[0]; } inline void build(int l, int r, int x) { if(l == r) { tree[x].ans = table[l]; return; } int mid = (l + r) >> 1; build(l, mid, x << 1); build(mid + 1, r, x << 1 | 1); tree[x].ans = (tree[x << 1].ans + tree[x << 1 | 1].ans) % phi[0]; } inline void update(int l, int r, int x, int a, int b) { //如果这次的幂和上次一样就不变了 if(tree[x].mn >= cnt) return; if(l > b || r < a) return; if(l == r) { ++tree[x].mn; tree[x].ans = calc(table[l], tree[x].mn); return; } int mid = (l + r) >> 1; update(l, mid, x << 1, a, b); update(mid + 1, r, x << 1 | 1, a, b); tree[x].mn = min(tree[x << 1].mn, tree[x << 1 | 1].mn); tree[x].ans = (tree[x << 1].ans + tree[x << 1 | 1].ans) % phi[0]; } inline ll query(int l, int r, int x, int a, int b) { if(l > b || r < a) return 0; if(l >= a && r <= b) return tree[x].ans % phi[0]; int mid = (l + r) >> 1, ret = 0; ret = (ret + query(l, mid, x << 1, a, b)) % phi[0]; ret = (ret + query(mid + 1, r, x << 1 | 1, a, b)) % phi[0]; return ret; } } using namespace seg; int main() { scanf("%d%d%lld%lld", &n, &m, &p, &c); phi[0] = p; ll P = p; while(P != 1) phi[++cnt] = P = getphi(P); phi[++cnt] = 1; for(int i = 1; i <= n; ++i) scanf("%lld", &table[i]); build(1, n, 1); while(m--) { int opt, l, r; scanf("%d", &opt); if(opt == 0) { scanf("%d%d", &l, &r); update(1, n, 1, l, r); } if(opt == 1) { scanf("%d%d", &l, &r); printf("%lld\n", query(1, n, 1, l, r)); } } return 0; }
bzoj4869
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。