cf448D Multiplication Table

D. Multiplication Table

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Bizon the Champion isn't just charming, he also is very smart.

While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann × m multiplication
table, where the element on the intersection of the i-th row and j-th
column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th
largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?

Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th
number you write out is called the k-th largest number.

Input

The single line contains integers n, m and k (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m).

Output

Print the k-th largest number in a n × m multiplication
table.

Sample test(s)

input

2 2 2

output

input

2 3 4

output

input

1 10 5

output

Note

A 2 × 3 multiplication table looks like this:

1 2 3

2 4 6

唉这么水的题竟然final test能wa

题意是已知一个固定的矩阵，其中第i行第j列是i*j，然后问在n*m的这样的矩阵中第k大是多少

首先矩阵是固定的，矩阵中数据的规模是2500e。这样的大小对于一般递推太大了些

但是二分+判定的做法还是很好想的

我们每次二分一个可能的第k大数，然后第i行所有小于等于它的数的个数是min(mid/i,m)（因为尽管一排中可能最多有mid/i个数，但是题目已经限定是n*m，直接加mid/i显然不对，我就是这里一开始第五个点wa），用这样的办法统计出所有小于它的数，就很好判定了

但是仅仅是这样还是不行。所以我final test wa了。为什么不行呢？注意到矩阵中并不包含所有正整数，并且显然除了第一行能凑出1到n、第一列可以凑出1到m之外，只有合数可以存在于矩阵中。但是由于二分一旦找到sum加起来等于k的时候就退出，于是会出现这样斯巴达的情况：

对于3*3的矩阵,我们求第8大：

1 2 3

2 4 6

3 6 9

我们二分1到9

第一次：mid=5，sum=6

第二次：mid=7，sum=8

此时sum=k，就应该退出了。但是显然7没有出现在矩阵中！所以问题出现了：有时会二分到不在矩阵中的数。

怎么处理呢？

我们在二分的时候加一个prime()函数，用来判定质数。如果mid<=n或者mid<=m或者mid是合数的时候，它才可能出现在矩阵中。

那么每次做prime()效率是sqrt(n*m)就是50w级的，每行搜过去更新sum是O(m)也是50w的，最多二分log(2500e)大概3、40次，是不会爆的

#include<bits/stdc++.h>

#include<iostream>

#define LL long long

using namespace std;

LL n,m,k,l,r,ans;

inline bool prime(LL x)

{

	if (x<2) return 0;

	for (int i=2;i*i<=x;i++)

	  if (x%i) return 0;

	return 1;

}

int main()

{

	scanf("%lld%lld%lld",&n,&m,&k);

	l=1;r=m*n;

	while (l<=r)

	{

		LL mid=(l+r)>>1,sum=0;

		bool mark=mid<=n||mid<=m||prime(mid);

		for (int j=1;j<=n;j++)

		{

		  sum+=min(mid/j,m);

	 	}

		if (sum==k&&mark)

		{

			printf("%lld",mid);

			return 0;

		}

		else

		{

			if (sum<k) l=mid+1;

			else

			{

				r=mid-1;

				ans=mid;

			}

		}

	}

	printf("%lld",ans);

}

巴特西

cf448D Multiplication Table

最新文章

热门文章