| 295 | } |
| 296 | |
| 297 | int fnroot(int n, int x) { |
| 298 | if (x < 2) |
| 299 | return x; |
| 300 | /* |
| 301 | * We look for l such that: l^n <= x < (l+1)^n |
| 302 | */ |
| 303 | long long int l = 1; |
| 304 | long long int u = x; |
| 305 | do { |
| 306 | long long int m = (l + u) >> 1; |
| 307 | if (powgr(n,m,x)) u=m; else l=m; |
| 308 | } while (l+1 < u); |
| 309 | return static_cast<int>(l); |
| 310 | } |
| 311 | |
| 312 | bool powle(int n, long long int r, int x) { |
| 313 | assert(r >= 0); |