如果按顺序排列一个NxM乘法表，那么中间的数字是什么? [英] If an NxM multiplication table is put in order, what is number in the middle?
问题描述
如果我有一个乘法表，例如3x5:
If I have a multiplication table sized, for example, 3x5:
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
然后我将所有这些数字按顺序排列:
And I put all these numbers in order:
1 2 2 3 3 4 4 5 6 6 8 9 10 12 15
中间的数字是多少?在这种情况下，它是5.
What is the number in the middle? In this case, it's 5.
N和M总是奇数，因此只能有一个答案.
N and M are always odd, so there can be only one answer.
是否有一个快速的解决方案?我正在寻找O(N log NM)
Is there a fast solution for this? I'm looking for something among the lines of O(N log NM)
这是各种各样的作业，但是我真的迷失了这个.我提出了一些想法，但是它们都有一些缺点:
This is homework of sorts, but I'm really lost with this one. I've come up with some ideas, but they all had some shortcomings:
public class Table {
public static void main(String[] ar) {
Scanner scanner = new Scanner(System.in);
int w = scanner.nextInt();
int h = scanner.nextInt();
int[] s = new int[w * h + 1];
for (int i = 1; i <= w; i++)
for (int j = 1; j <= h; j++)
s[i * j] = s[i * j] + 1;
int sum = 0;
for (int i = 0; i < s.length; i++) {
sum += s[i];
if (sum >= s.length / 2) {
System.out.println(i);
break;
}
}
}
}
这可以足够快地(<4s)解决大多数测试，但是对于大的N和M，则超出了内存限制(我不知道确切的限制).
This solves most of the tests fast enough (<4s), but for big N and M, the memory limits are exceeded (I don't know the exact limitations).
这个想法是跟踪每个数字的出现次数，然后依次遍历所有数字，并在每次迭代中添加出现的次数.当出现次数大于或等于w * h / 2时，它是中间的数字，我们将其打印出来.
The idea is to keep track of the occurrences of each number, and then iterate through all the numbers in order, adding the number of occurrences each iteration. When the number of occurrences is higher or equal to w * h / 2, it is the number in the middle and we print it.
public class Table {
public static void main(String[] ar) {
Scanner scanner = new Scanner(System.in);
int w = scanner.nextInt();
int h = scanner.nextInt();
int sum = 0;
for (int i = 1; i <= w * h; i++) {
for (int j = 1; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
int k = i / j;
if (k <= w && k != j) sum++;
if (k <= h && k != j) sum++;
if (k <= w && k <= h && k == j) sum++;
}
}
if (sum >= (w * h + 1) / 2) {
System.out.println(i);
break;
}
}
}
}
试图克服内存限制，我尝试对每个数字的出现进行计数，直到它们出现为止.我注意到，每个数字的乘法表中的出现次数就是它们具有的因子的数量.
Trying to overcome the memory limits, I tried counting the occurrences of each number up to the middle one as they come. I noticed that the number of occurrences in a multiplication table of each number is the number of factors they have.
不够快.
任何人都可以提出任何建议吗?我知道在建议的O(N log NM)解决方案中使用了二进制搜索.
Can anyone come up with any pointers? I know that in the suggested O(N log NM) solution binary search is used.
1 <= N <= 10^5
1 <= M <= 10^5
解决方案！
好的，因此，感谢@PeterdeRivaz，我得以找到并实施针对我的问题的解决方案.这个想法正如他所描述的那样，这里是实际的实现:
Solution!
Ok, so thanks to @PeterdeRivaz I was able to find and implement a solution for my problem. The idea is as he describes it, and here's the actual implementation:
public class Kertotaulu {
public static void main(String[] ar) {
Scanner scanner = new Scanner(System.in);
long h = scanner.nextLong();
long w = scanner.nextLong();
long min = 1;
long max = w*h;
long mid = 0;
while (min <= max) {
mid = (min + max) / 2;
long sum = 0;
for (int i = 1; i <= h; i++) sum += Math.min(mid / i, w);
sum--;
if (sum < (w * h) / 2) min = mid + 1;
else if (sum > (w * h) / 2) max = mid - 1;
else break;
}
long sum = 0;
for (int i = 1; i <= h; i++) sum += Math.min((mid - 1) / i, w);
sum--;
if (sum == (w * h) / 2) System.out.println(mid - 1);
else System.out.println(mid);
}
}
推荐答案
您可以通过对乘法表中小于该值的条目进行计数来对值进行二进制搜索.
You can use binary search on the value by counting how many entries in the multiplication table will be less than the value.
这将需要在二进制搜索中进行log(NM)迭代，因此我们需要能够以O(N)计算总复杂度为O(Nlog(NM))的计数.
This will require log(NM) iterations in the binary search so we need to be able to compute the count in O(N) for a total complexity of O(Nlog(NM)).
这可以通过依次考虑每个乘法表来完成.例如，假设我们的测试值为8，我们正在考虑3倍表.
This can be done by considering each multiplication table in turn. For example, suppose our test value is 8 and we are considering the 3 times table.
小于8的值将是3 * 1和3 * 2.我们可以通过简单地将测试值8除以表3并四舍五入来找到有多少，即floor(8/3)= 2，因此3倍表将得出2.
The values less than eight will be 3*1 and 3*2. We can find how many there are by simply dividing the test value 8 by the table 3 and rounding down, i.e. floor(8/3) = 2 so the 3 times table will give us a count of 2.
这篇关于如果按顺序排列一个NxM乘法表，那么中间的数字是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
