// UVa 11226 - Reaching the fix-point #include <iostream> #include <stdio.h> #include <cmath> using namespace std; #define datatype unsigned long int #define p2 524288 datatype sopf[500001]; unsigned int lsopf[500001]; unsigned int tree[1048576]; void insert(datatype node, datatype ini, datatype fin, datatype i, unsigned int v) { tree[node] = max(tree[node], v); if (ini == fin) return; datatype mid = (ini + fin) >> 1; if (mid < i) insert(node * 2 + 1, mid + 1, fin, i, v); else insert(node << 1, ini, mid, i, v); } int get(datatype node, datatype ini, datatype fin, datatype a, datatype b) { if (a == ini && b == fin) return tree[node]; datatype mid = (ini + fin) >> 1; if (a > mid) return get(node * 2 + 1, mid + 1, fin, a, b); else if (b <= mid) return get(node << 1, ini, mid, a, b); else { unsigned int lf = get(node << 1, ini, mid, a, mid); unsigned int rg = get(node * 2 + 1, mid + 1, fin, mid + 1, b); return max(lf, rg); } } int main() { for (datatype i = 2; i < 500001; i++) { datatype sqrti = sqrt(i); bool prime = true; for (datatype j = 2; j <= sqrti; j++) { lsopf[i] = 0; if (i % j == 0) { sopf[i] = sopf[i / j] + j; lsopf[i] = lsopf[sopf[i]] + 1; prime = false; break; } } if (prime) { sopf[i] = i; lsopf[i] = 1; } insert(1, 1, p2, i, lsopf[i]); } int tt; cin >> tt; for (int t = 1; t <= tt; t++) { datatype n, m; cin >> n >> m; if (n > m) { datatype tmp = n; n = m; m = tmp; } unsigned int mx = get(1, 1, p2, n, m); printf("Case #%d:\n%u\n", t, mx); } return 0; }
Monday, November 30, 2015
UVa 11226 - Reaching the fix-point
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment