UVA 10909 - Lucky Number(树状数组)

本文主要是介绍UVA 10909 - Lucky Number(树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 10909 - Lucky Number

题目链接

题意：问一个数字能否由两个lucky num构造出来，lucky num根据题目中的定义

思路：利用树状数组找前k大的方法可以构造出lucky num的序列，然后每次查找n，就从n / 2开始往下查找即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 2000001;int bit[N], tmp[N], lucky[N], vis[N], tot;int lowbit(int x) {return (x&(-x));
}void add(int x, int v) {while (x < N) {bit[x] += v;x += lowbit(x);}
}int n;int find(int x) {int ans = 0, num = 0;for (int i = 20; i >= 0; i--) {ans += (1<<i);if (ans >= N || num + bit[ans] >= x)ans -= (1<<i);else num += bit[ans];}return ans + 1;
}void solve(int n) {if (n % 2 == 0) {int i = upper_bound(lucky + 1, lucky + tot + 1,  n / 2) - lucky - 1;for (; i >= 1; i--) {if (vis[n - lucky[i]]) {printf("%d is the sum of %d and %d.\n", n, lucky[i], n - lucky[i]);return;}}}printf("%d is not the sum of two luckies!\n", n);
}int main() {tot = 2000000;for (int i = 1; i <= tot; i += 2)add(i, 1);tot /= 2;for (int i = 2; ; i++) {int len = find(i);if (tot < len) break;for (int j = len; j <= tot; j += len)tmp[j] = find(j);for (int j = len; j <= tot; j += len)add(tmp[j], -1);tot = tot - tot / len;}for (int i = 1; i <= tot; i++) {lucky[i] = find(i);vis[lucky[i]] = 1;}while (~scanf("%d", &n)) {solve(n);}return 0;
}

这篇关于UVA 10909 - Lucky Number(树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---