给出两个数字,x并y找到无数字的数字,其中squarefree数是一个可被除尽的完美正方形除外1.例如,10是无方形但18不是,因为它可被整除9 = 32.很少有正方形数字是:
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15 ...
范围
1 <= X,Y <= 10^9
0 <= |X-Y| <= 10^6
x=10 , Y=15
给
ans=5
我的方法是生成所有素数直到squareroot(10^9)(eratosthenes的筛子),并检查给定范围内的每个数字是否可被素数平方整除.从范围长度中减去这些数字的数量,得到平方自由数.
但这种方法的复杂性超时,请提出其他一些方法
找到 n*n 2D 矩阵的元素的最小总和，这样我必须从每一行和每列中选择一个且仅一个元素？例如
4 12
6 6
如果我4从 row 中选择，1我不能12从 row1 也从 column 中1选择，我只能从第 2 行第 2 列中选择 6。
所以，同样的最低金额是4 + 6 = 10其中6从第二行第二列
而不是6 + 12 = 18其中6是从第二行第一列
也4 + 12不允许，因为两者都来自同一行
我想到了蛮力，一旦我从行和列中选择元素，我就无法选择另一个，但这种方法是O(n!)
.