链接:https://www.nowcoder.com/acm/contest/205/L
来源:牛客网
题目描述
终于活成了自己讨厌的样子。
这是她们都还没长大的时候发生的故事。那个时候,栗子米也不需要为了所谓的爱情苦恼。
她们可以在夏日的午后,花大把的时间去研究生活中一些琐碎而有趣的事情,比如数论。
有一天西柚柚问了栗子米一个题,她想知道中有多少不同的数,这些不同的数字里面第k大的是多少。
输入描述:
第一行一个整数T(T≤ 105),表示数据组数。
每组数据第一行两个整数,表示n,k(1≤ n≤ 1018),保证k不会超过不同的数字个数。
输出描述:
对于每组数据输出,输出两个整数,表示有多少个不同的数字和这里面第k大的是多少。
示例1
输入
复制
3
1 1
5 2
67 8
输出
复制
1 1
3 2
15 8
自闭的签到题…暴力解决不了问题
打表找规律,然后个数就是上oeis找了个式子sqrt(4*n+1)-1
然后第k个本来我是想大于cnt/2的就直接按cnt-k+1算,因为后面cnt/2个肯定是连续的,而前面那一段离散的我是用整除分块的方法,但是还是超时了,然后队友想出离散的直接n/k就好了…
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=1e8+50;
bool vis[N];
typedef long long ll;
ll n,k;
int t;
int main(void){
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&n,&k);
ll cnt=ll(sqrt(4*n+1))-1;
ll ans=0;
if(k>cnt/2){
ans=cnt-k+1;
}
else{
ans=n/k;
}
printf("%lld %lld\n",cnt,ans);
return 0;
}