本文共 5420 字,大约阅读时间需要 18 分钟。
题目链接:
题目大意:
终于活成了自己讨厌的样子。 这是她们都还没长大的时候发生的故事。那个时候,栗子米也不需要为了所谓的爱情苦恼。 她们可以在夏日的午后,花大把的时间去研究生活中一些琐碎而有趣的事情,比如数论。 有一天西柚柚问了栗子米一个题,她想知道中有多少不同的数,这些不同的数字里面第k大的是多少。题解:
上来思路不是很明确,于是打个表,看一下不同的数的个数
1 -------1 1个
2 1 -------2 2个 3 1 -------3 2个 4 2 1 -------4 3个 5 2 1 -------5 3个 6 3 2 1 -------6 4个 7 3 2 1 -------7 4个 8 4 2 1 -------8 4个 9 4 3 2 1 -------9 5个 10 5 3 2 1 -------10 5个 11 5 3 2 1 -------11 5个 12 6 4 3 2 1 -------12 6个 13 6 4 3 2 1 -------13 6个 14 7 4 3 2 1 -------14 6个 15 7 5 3 2 1 -------15 6个 16 8 5 4 3 2 1 -------16 7个 17 8 5 4 3 2 1 -------17 7个 18 9 6 4 3 2 1 -------18 7个 19 9 6 4 3 2 1 -------19 7个 20 10 6 5 4 3 2 1 -------20 8个 21 10 7 5 4 3 2 1 -------21 8个 22 11 7 5 4 3 2 1 -------22 8个 23 11 7 5 4 3 2 1 -------23 8个 24 12 8 6 4 3 2 1 -------24 8个 25 12 8 6 5 4 3 2 1 -------25 9个 26 13 8 6 5 4 3 2 1 -------26 9个 27 13 9 6 5 4 3 2 1 -------27 9个 28 14 9 7 5 4 3 2 1 -------28 9个 29 14 9 7 5 4 3 2 1 -------29 9个 30 15 10 7 6 5 4 3 2 1 -------30 10个 31 15 10 7 6 5 4 3 2 1 -------31 10个 32 16 10 8 6 5 4 3 2 1 -------32 10个 33 16 11 8 6 5 4 3 2 1 -------33 10个 34 17 11 8 6 5 4 3 2 1 -------34 10个 35 17 11 8 7 5 4 3 2 1 -------35 10个 36 18 12 9 7 6 5 4 3 2 1 -------36 11个 37 18 12 9 7 6 5 4 3 2 1 -------37 11个 38 19 12 9 7 6 5 4 3 2 1 -------38 11个 39 19 13 9 7 6 5 4 3 2 1 -------39 11个 40 20 13 10 8 6 5 4 3 2 1 -------40 11个 41 20 13 10 8 6 5 4 3 2 1 -------41 11个 42 21 14 10 8 7 6 5 4 3 2 1 -------42 12个 43 21 14 10 8 7 6 5 4 3 2 1 -------43 12个 44 22 14 11 8 7 6 5 4 3 2 1 -------44 12个 45 22 15 11 9 7 6 5 4 3 2 1 -------45 12个 46 23 15 11 9 7 6 5 4 3 2 1 -------46 12个 47 23 15 11 9 7 6 5 4 3 2 1 -------47 12个 48 24 16 12 9 8 6 5 4 3 2 1 -------48 12个 49 24 16 12 9 8 7 6 5 4 3 2 1 -------49 13个 50 25 16 12 10 8 7 6 5 4 3 2 1 -------50 13个 51 25 17 12 10 8 7 6 5 4 3 2 1 -------51 13个 52 26 17 13 10 8 7 6 5 4 3 2 1 -------52 13个 53 26 17 13 10 8 7 6 5 4 3 2 1 -------53 13个 54 27 18 13 10 9 7 6 5 4 3 2 1 -------54 13个 55 27 18 13 11 9 7 6 5 4 3 2 1 -------55 13个 56 28 18 14 11 9 8 7 6 5 4 3 2 1 -------56 14个 57 28 19 14 11 9 8 7 6 5 4 3 2 1 -------57 14个 58 29 19 14 11 9 8 7 6 5 4 3 2 1 -------58 14个 59 29 19 14 11 9 8 7 6 5 4 3 2 1 -------59 14个 60 30 20 15 12 10 8 7 6 5 4 3 2 1 -------60 14个 61 30 20 15 12 10 8 7 6 5 4 3 2 1 -------61 14个 62 31 20 15 12 10 8 7 6 5 4 3 2 1 -------62 14个 63 31 21 15 12 10 9 7 6 5 4 3 2 1 -------63 14个 64 32 21 16 12 10 9 8 7 6 5 4 3 2 1 -------64 15个 65 32 21 16 13 10 9 8 7 6 5 4 3 2 1 -------65 15个 66 33 22 16 13 11 9 8 7 6 5 4 3 2 1 -------66 15个 67 33 22 16 13 11 9 8 7 6 5 4 3 2 1 -------67 15个 68 34 22 17 13 11 9 8 7 6 5 4 3 2 1 -------68 15个 69 34 23 17 13 11 9 8 7 6 5 4 3 2 1 -------69 15个 70 35 23 17 14 11 10 8 7 6 5 4 3 2 1 -------70 15个 71 35 23 17 14 11 10 8 7 6 5 4 3 2 1 -------71 15个 72 36 24 18 14 12 10 9 8 7 6 5 4 3 2 1 -------72 16个 73 36 24 18 14 12 10 9 8 7 6 5 4 3 2 1 -------73 16个 74 37 24 18 14 12 10 9 8 7 6 5 4 3 2 1 -------74 16个 75 37 25 18 15 12 10 9 8 7 6 5 4 3 2 1 -------75 16个 76 38 25 19 15 12 10 9 8 7 6 5 4 3 2 1 -------76 16个 77 38 25 19 15 12 11 9 8 7 6 5 4 3 2 1 -------77 16个 78 39 26 19 15 13 11 9 8 7 6 5 4 3 2 1 -------78 16个 79 39 26 19 15 13 11 9 8 7 6 5 4 3 2 1 -------79 16个 80 40 26 20 16 13 11 10 8 7 6 5 4 3 2 1 -------80 16个 81 40 27 20 16 13 11 10 9 8 7 6 5 4 3 2 1 -------81 17个 82 41 27 20 16 13 11 10 9 8 7 6 5 4 3 2 1 -------82 17个 83 41 27 20 16 13 11 10 9 8 7 6 5 4 3 2 1 -------83 17个 84 42 28 21 16 14 12 10 9 8 7 6 5 4 3 2 1 -------84 17个 85 42 28 21 17 14 12 10 9 8 7 6 5 4 3 2 1 -------85 17个 86 43 28 21 17 14 12 10 9 8 7 6 5 4 3 2 1 -------86 17个 87 43 29 21 17 14 12 10 9 8 7 6 5 4 3 2 1 -------87 17个 88 44 29 22 17 14 12 11 9 8 7 6 5 4 3 2 1 -------88 17个 89 44 29 22 17 14 12 11 9 8 7 6 5 4 3 2 1 -------89 17个 90 45 30 22 18 15 12 11 10 9 8 7 6 5 4 3 2 1 -------90 18个 91 45 30 22 18 15 13 11 10 9 8 7 6 5 4 3 2 1 -------91 18个 92 46 30 23 18 15 13 11 10 9 8 7 6 5 4 3 2 1 -------92 18个 93 46 31 23 18 15 13 11 10 9 8 7 6 5 4 3 2 1 -------93 18个 94 47 31 23 18 15 13 11 10 9 8 7 6 5 4 3 2 1 -------94 18个 95 47 31 23 19 15 13 11 10 9 8 7 6 5 4 3 2 1 -------95 18个 96 48 32 24 19 16 13 12 10 9 8 7 6 5 4 3 2 1 -------96 18个 97 48 32 24 19 16 13 12 10 9 8 7 6 5 4 3 2 1 -------97 18个 98 49 32 24 19 16 14 12 10 9 8 7 6 5 4 3 2 1 -------98 18个 99 49 33 24 19 16 14 12 11 9 8 7 6 5 4 3 2 1 -------99 18个 100 50 33 25 20 16 14 12 11 10 9 8 7 6 5 4 3 2 1 -------100 19个发现在25,36,49,64,81这些点不同数的个数都会加1,然后对于开根号的值相等的一段数中
比如n=64~80,这一段数中 都是8,在每一段这样的数中,不同的数的个数也分两段,后一段比前一段多1,进而我发现,分界点是.对于n=64~80,前一段不同数的个数是15=,后一段是16=
设这些不同的数的个数为m,以m/2为分界线(在这里比如64-80这一段是要看80的,如果看70的话可能不到m/2,从第5项就开始递减了,但这是恰好对上的),如果k在前一半,那么第k大的数就是n/k
如果k在后一半,那就是m/2到1中倒着数的第k-m/2个,即
打表的时候可能会掉入一个坑:队友用set存的,结果最后显示的都是排了序的,所以没看出规律
#includeusing namespace std;#define mod 998244353typedef long long ll;int main(){// int T; int T; scanf("%d",&T); ll n,k; while(T--) { scanf("%lld%lld",&n,&k); ll q=sqrt(n),m; if(n>=q*(q+1)) m=2*q; else m=2*q-1; if(k<=m/2) printf("%lld %lld\n",m,n/k); else printf("%lld %lld\n",m,m-k+1); } return 0;}
打表程序
#includeusing namespace std;#define mod 998244353typedef long long ll;int main(){// freopen("input.txt","r",stdin); for(int n=1; n<=100; ++n) { int pre=-1; int num=0; for(int i=1; i<=n; ++i) { if(n/i!=pre) cout<
转载地址:http://fkfgf.baihongyu.com/