给定一个数字 K,它是两个不同数字 (A,B) 的乘积,找到最大数字 (<=A & <=B) whose square divides the K.
)例如:K = 54 (6*9)。这两个数字都可用,即 6 和 9。
我的方法非常简单或微不足道。
对于给定的示例,3*3 = 9 除 K,因此答案为 3。
寻找比平凡解决方案更好的算法。
注意: 测试用例有 1000 个,因此需要最好的方法。
我相信其他人会想出一个涉及模运算的好答案。 这是一个幼稚的方法...
每个因子本身都可以被分解(尽管这可能是一个昂贵的操作)。
给定这些因素,您就可以寻找重复因素组。
例如,使用您的示例:
9 的质因数:3, 3
6 的质因数:2, 3
所有质因数:2, 3, 3, 3
有两个 3,所以你就有了答案(3 的平方除以 54)。
第二个例子 36 x 9 = 324
36 的质因数:2,2,3,3
9 的质因数:3, 3
所有质因数:2, 2, 3, 3, 3, 3
所以有两个 2 和四个 3,这意味着 2x3x3 是重复的。 2x3x3 = 18,所以 18 的平方除以 324。
编辑:python原型
import math
def factors(num, dict):
""" This finds the factors of a number recursively.
It is not the most efficient algorithm, and I
have not tested it a lot. You should probably
use another one. dict is a dictionary which looks
like {factor: occurrences, factor: occurrences, ...}
It must contain at least {2: 0} but need not have
any other pre-populated elements. Factors will be added
to this dictionary as they are found.
"""
while (num % 2 == 0):
num /= 2
dict[2] += 1
i = 3
found = False
while (not found and (i <= int(math.sqrt(num)))):
if (num % i == 0):
found = True
factors(i, dict)
factors(num / i, dict)
else:
i += 2
if (not found):
if (num in dict.keys()):
dict[num] += 1
else:
dict[num] = 1
return 0
#MAIN ROUTINE IS HERE
n1 = 37 # first number (6 in your example)
n2 = 41 # second number (9 in your example)
dict = {2: 0} # initialise factors (start with "no factors of 2")
factors(n1, dict) # find the factors of f1 and add them to the list
factors(n2, dict) # find the factors of f2 and add them to the list
sqfac = 1
# now find all factors repeated twice and multiply them together
for k in dict.keys():
dict[k] /= 2
sqfac *= k ** dict[k]
# here is the result
print(sqfac)
C++答案
int func(int i, j)
{
int k = 54
float result = pow(i, 2)/k
if (static_cast<int>(result)) == result)
{
if(i < j)
{
func(j, i);
}
else
{
cout << "Number is correct: " << i << endl;
}
}
else
{
cout << "Number is wrong" << endl;
func(j, i)
}
}
说明:
首先递归,然后测试结果是否为正整数,如果是,然后检查另一个倍数是否小于或大于,如果更大的递归函数尝试另一个倍数,如果不是,则它是正确的。然后,如果结果不是正整数,则打印 Number 错误,并执行另一个递归函数来测试 j。
如果我的问题正确,我会看到你有一个长度=A,宽度=B,面积=K的矩形 你想把它转换成正方形并失去尽可能小的面积
如果是这样的话。因此,您的算法的问题不在于多次迭代直到获得输出的成本。 相反,问题在于您的算法很大程度上取决于输入矩形的长度 A 和宽度 B。 虽然它应该只取决于面积 K
例如:
因此,在我的解决方案中,我假设单个输入 K
我的想法如下
这可能需要额外的迭代,但会保证准确的答案 另外,可能有人担心 sqrt(K) 的成本 但它只会被调用一次,以避免误导长度和宽度输入
如果您对 K 进行素因式分解,则可以轻松找到 K 的最大平方因数。然而,这是一个昂贵的操作,但如果您已经知道对于已知的 A 和 B,K = A*B,则 A 和 B 的因式分解然后可以很容易地组合起来得到 K 的素因数分解。For
K = prod_{p prime | K} p_i^{e_i}
gsd(K) = prod_{p prime | K} p_i^{e_i - {e_i & 1}}
其中,当 e_i 为奇数时,{e_i & 1} 为 1,否则为零。
对于足够小的整数,例如64 位,可以通过试除法高效计算根式直至立方根,而无需了解完整的素因数分解。请参阅整数的最大无平方除数(又称根式)算法。假设你知道 A 和 B 的部首,那么
rad = radical(K) = radical(A)*radical(B) / gcd(radical(A), radical(B))
可以使用以下算法从根式有效计算 K 的最大平方除数。
function gsdfromradical(K, rad) {
if (K <= 1) return K
w = gcd(rad, K/rad)
v = K
u = 2
while (u > 1)
u = gcd(v, w)
v /= u
x = K/(v*w*w)
if (x == 1) return w*w
return w*w*(gsdfromradical(x, gcd(rad, x)))