2733. [郑州集训 2017]NOI模拟题2.1

【题目描述】

小火车觉得对生活已经没有什么好留恋的了，于是决定前往二次

元去寻找真爱。

二次元有很多很多的妹子，但哪些才是真爱呢？

小火车把她们从1 到n 标上号，第i 个妹子对小火车的好感度为

1 当且仅当i 不包含除1 以外的平方因子，且质因数分解由偶数个素

数组成，好感度为-1 当且仅当i 不包含除1 以外的平方因子，且质

因数分解由奇数个素数组成，否则好感度为0。特别的1 号妹子好感

度为1。(实际上就是莫比乌斯函数)

小火车知道他的后宫是由标号为1 到k 的妹子组成的，但他不记

得k 是多少了，只记得好感度之和为m，现在告诉你m，能给出一个

合法的k 吗，或者说，小火车只是在空想？

【输入格式】

一行两个整数n 和m，含义如题所述。

【输出格式】

一行一个正整数表示一个合法的k，如果在n 以内不存在这样的k

输出-1。

【样例输入】

10 -2

【样例输出】

5

【提示】

对于20%的数据n=100000；

对于另外30%的数据n=10000000；

对于另外50%的数据n=1000000000。

【来源】

吴作凡