首页 > 代码库 > hdu 5152 A Strange Problem线段树+欧拉函数
hdu 5152 A Strange Problem线段树+欧拉函数
*****************************************BC题解**********************************************************************
1003 A Strange Problem对于操作二，利用公式当x >= Phi(C), A^x = A ^ (x%Phi(C) + Phi(C)) (mod C)对于2333333这个模数来说，求18次欧拉函数后就变成了1，所以只需要保存19层第三次操作的加数即可，然后就直接是线段树区间更新和询问操作了。Ps:很多人把题目想简单了，操作二不能直接简单的更新，不满足2^(2^x) mod P = 2^( 2^x mod P) mod P。
*********************************************************************************************************************
辅助公式：
a^b=a^(b%phi(c)+phi(c))(mod c);
phi(c)为1~c中，与c互质的数的个数。
((a^b)^c)=a^(b^c)
a^(b^c)=a^(b^c%phi(c)+phi(c)) (mod c);
b^c%phi(c)=b^(c%phi(phi(c))+phi(phi(c)));
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 #include <ctime> 6 #include <iostream> 7 using namespace std; 8 9 typedef __int64 ll; 10 const int MOD = 2333333; 11 const int N = 50000+5; 12 13 int mo[20] = {2333333,2196720,580608,165888,55296,18432, 14 6144,2048,1024,512,256,128,64,32,16,8,4,2,1}; 15 int pow2[33]; 16 17 vector<ll> vt[N]; 18 struct Segtree { 19 #define lson rt<<1, l, mid 20 #define rson rt<<1|1, mid+1, r 21 ll mark[N<<2]; 22 int length[N<<2], sum[N<<2]; 23 void build(int rt, int l, int r) { 24 mark[rt] = 0; 25 length[rt] = r-l+1; 26 if(l == r) { 27 vt[l].clear(); 28 int x; 29 scanf("%d", &x); 30 vt[l].push_back(x); 31 sum[rt] = x%MOD; 32 return ; 33 } 34 int mid = l+r>>1; 35 build(lson); build(rson); 36 up(rt); 37 } 38 39 inline void Add(int &x, int y) { 40 x += y; 41 if(x >= MOD) x -= MOD; 42 } 43 44 void up(int rt) { 45 sum[rt] = sum[rt<<1] + sum[rt<<1|1]; 46 Add(sum[rt], 0); 47 } 48 49 void down(int rt) { 50 if(mark[rt]) { 51 mark[rt<<1] += mark[rt]; 52 mark[rt<<1|1] += mark[rt]; 53 Add(sum[rt<<1], 1LL*length[rt<<1]*mark[rt]%MOD); 54 Add(sum[rt<<1|1], 1LL*length[rt<<1|1]*mark[rt]%MOD); 55 mark[rt] = 0; 56 } 57 } 58 59 void update(int rt, int l, int r, int L, int R, int v) { 60 if(L <= l && R >= r) { 61 mark[rt] += v; 62 Add(sum[rt], 1LL*length[rt]*v%MOD); 63 return ; 64 } 65 down(rt); 66 int mid = l+r>>1; 67 if(L <= mid) update(lson, L, R, v); 68 if(R > mid) update(rson, L, R, v); 69 up(rt); 70 } 71 72 int pow_mod(int x, int n, int mod) { 73 int ret = 1%mod; 74 while(n) { 75 if(n&1) ret = 1LL*ret*x%mod; 76 x = 1LL*x*x%mod; 77 n >>= 1; 78 } 79 return ret; 80 } 81 82 int cal(vector<ll> &v) { 83 if(v.size() < 19) { 84 int pos = v.size()-1; 85 ll ret = v[0]; 86 bool flag = false; 87 if(v[0] >= mo[pos]) { 88 flag = true; 89 ret = ret%mo[pos] + mo[pos]; 90 } 91 pos--; 92 for(int i = 1;i < v.size(); i++) { 93 if(flag) { 94 ret = (pow_mod(2, ret, mo[pos]) +v[i])%mo[pos] + mo[pos]; 95 } 96 else { 97 if(ret >= 30) { 98 flag = true; 99 ret = (pow_mod(2, ret, mo[pos]) + v[i])%mo[pos]+mo[pos];100 }101 else if(pow2[ret] >= mo[pos]) {102 flag = true;103 ret = (pow_mod(2, ret, mo[pos]) + v[i])%mo[pos] + mo[pos];104 }105 else {106 ret = pow2[ret] + v[i];107 if(ret >= mo[pos]) {108 flag = true;109 ret = ret%mo[pos] + mo[pos];110 }111 }112 }113 pos--;114 }115 return ret%MOD;116 }117 else {118 ll ret = 1;119 int pos = 18;120 bool flag = true;121 for(int i = v.size()-18;i < v.size(); i++) {122 ret = (pow_mod(2, ret, mo[pos]) + v[i])%mo[pos] + mo[pos];123 pos--;124 }125 return ret%MOD;126 }127 }128 129 void modify(int rt, int l, int r, int x) {130 if(l == r) {131 if(mark[rt]) {132 vt[l][vt[l].size()-1] += mark[rt];133 mark[rt] = 0;134 }135 vt[l].push_back(0);136 sum[rt] = cal(vt[l]);137 return ;138 }139 down(rt);140 int mid = l+r>>1;141 if(x <= mid) modify(lson, x);142 else modify(rson, x);143 up(rt);144 }145 146 int query(int rt, int l, int r, int L, int R) {147 if(L <= l && R >= r) return sum[rt];148 down(rt);149 int mid = l+r>>1, ret = 0;150 if(L <= mid) Add(ret, query(lson, L, R));151 if(R > mid) Add(ret, query(rson, L, R));152 up(rt);153 return ret;154 }155 }tree;156 157 int n, m;158 159 void init() {160 for(int i = 0;i <= 30; i++) pow2[i] = 1<<i;161 }162 163 int main() {164 init();165 int op, l, r, x;166 while(scanf("%d%d", &n, &m) == 2) {167 tree.build(1, 1, n);168 while(m--) {169 scanf("%d", &op);170 if(op == 1) {171 scanf("%d%d", &l, &r);172 printf("%d\n", tree.query(1, 1, n, l, r));173 }174 else if(op == 2) {175 scanf("%d", &x);176 tree.modify(1, 1, n, x);177 }178 else {179 scanf("%d%d%d", &l, &r, &x);180 tree.update(1, 1, n, l, r, x);181 }182 }183 }184 return 0;185 }
还没看懂数论那部分怎么搞的。。
hdu 5152 A Strange Problem线段树+欧拉函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。