| 42 | rep(i,0,l<<1) y[i] = y[i]*2 - T1[i] * y[i] * y[i]; |
| 43 | ntt(y, l<<1, true); } |
| 44 | void sqrt(Num x[], Num y[], int l) { |
| 45 | if (l == 1) { assert(x[0].x == 1); y[0] = 1; return; } |
| 46 | sqrt(x, y, l>>1); |
| 47 | inv(y, T2, l>>1); |
| 48 | rep(i,l>>1,l<<1) T1[i] = T2[i] = 0; |
| 49 | rep(i,0,l) T1[i] = x[i]; |
| 50 | ntt(T2, l<<1); ntt(T1, l<<1); |
| 51 | rep(i,0,l<<1) T2[i] = T1[i] * T2[i]; |
| 52 | ntt(T2, l<<1, true); |
| 53 | rep(i,0,l) y[i] = (y[i] + T2[i]) * inv2; } |
| 54 | // vim: cc=60 ts=2 sts=2 sw=2: |