南京网站排名外包,做办公家具在哪个网站推销好,忘记wordpress密码,一家只做直购的网站http://www.lydsy.com/JudgeOnline/problem.php?id4869 终于A了。。。参考了下dalao的代码。。。 拓展欧几里得定理#xff0c;改了几次就不变了#xff0c;但是用的时候要在快速幂里判是不是要用。 #includebits/stdc.h
using namespace std;
typedef long long ll… http://www.lydsy.com/JudgeOnline/problem.php?id4869 终于A了。。。参考了下dalao的代码。。。 拓展欧几里得定理改了几次就不变了但是用的时候要在快速幂里判是不是要用。 #includebits/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;
} View Code 转载于:https://www.cnblogs.com/19992147orz/p/6832433.html
