一种方法是计算他们的gcd并检查它是否为1.
有更快的方法吗？
我有两个号码,x1而且x2.对于一个数字y,我想计算公约数x1和x2尽可能接近的公约数y.
有一个有效的算法吗？
我认为现在是时候重新解决我的问题并且更清楚了.这不是关于整数...所以,我们有两个数字x1和x2.比如说,用户输入一个数字y.我想要找到的是一个y'接近的数字y,x1 % y'并且x2 % y'非常小(0.02例如,小于,但我们可以调用这个数字LIMIT).换句话说,我不需要最优算法,但需要很好的近似.
我感谢你们所有的时间和精力,非常友好!
下面的代码完美无缺,但我希望有人向我解释它背后的数学.基本上,它是如何工作的？
#include <stdio.h>
#include <stdlib.h> /* atoi */
#define min(x, y) (((x) < (y)) ? (x) : (y))
int main(int argc, char* argv[])
{
const int base = 16;
int n,i,j,p,c,noz,k;
n = 7; /* 7! = decimal 5040 or 0x13B0 - 1 trailing zero */
noz = n;
j = base;
/* Why do we start from 2 */
for (i=2; i <= base; i++)
{
if (j % i == 0)
{
p = 0; /* What is …我必须为a,b,m <2 ^ 32的大值有效地计算^^ b mod m,
其中^^是tetration运算符:2 ^^ 4 = 2 ^(2 ^(2 ^ 2))
m不是素数而不是10的幂.
你能帮我吗？
所以我有一个整数,例如1234567890和一组给定的数字,例如{4,7,18,32,57,68}
问题是1234567890是否可以由给定的数字组成(您可以使用多个数字,而不必使用所有数字).在上面的情况中,一种解决方案是:
38580246*32 + 1*18
(不需要提供具体的解决方案,只有在可以完成的情况下)
我的想法是尝试所有解决方案.例如,我会尝试
1*4*+ 0*7 + 0*18 + 0*32 + 0*57 + 0*68 = 4
2*4*+ 0*7 + 0*18 + 0*32 + 0*57 + 0*68 = 8
3*4*+ 0*7 + 0*18 + 0*32 + 0*57 + 0*68 = 12
.....
308 641 972*4*+ 0*7 + 0*18 + 0*32 + 0*57 + 0*68 = 1234567888
308 641 973*4*+ 0*7 + 0*18 + 0*32 + 0*57 + 0*68 = 1234567892 ==>超过
0*4*+ 1*7 + 0*18 + …
吸血鬼号码在这里定义https://en.wikipedia.org/wiki/Vampire_number.数字V是吸血鬼号码,如果:
我提出了一个解决方案,
strV = sort(toString(V))
for factor <- pow(10, N/2) to sqrt(V)
if factor divides V
X <- factor
Y <- V/factor
if X and Y have trailing zeros
continue
checkStr = sort(toString(X) + toString(Y))
if checkStr equals strV return true
另一种可能的解决方案是置换由V表示的字符串并将其分成两半并检查它是否是吸血鬼号码.哪一个是最好的方法呢？
对于给定的整数,n并m确定x^mterm in的系数(x^2+x+1)^n是偶数还是奇数？
例如,如果n = 3且m = 4 (x^2+x+1)^3 = x^6 + 3x^5 + [[6x^4]] + 7x^3 + 6x^2 + 3x + 1,那么项的系数x^4是6(=偶数).
n并且m大到10 ^ 12并且我想在几秒钟内计算,因此您无法在线性时间内计算.
你有任何有效的算法吗？
注意：这可能涉及大量的数论，但我在网上找到的公式只是一个近似值，所以我相信一个精确的解决方案需要计算机进行某种迭代计算。
我的目标是找到一种有效的算法（就时间复杂度而言）来解决大 n 值的以下问题：
令 R(a,b) 是欧几里德算法为找到非负整数 a 和 b 的 GCD 所采取的步数。即 R(a,b) = 1 + R(b,a%b)，且 R(a,0) = 0。给定一个自然数 n，求所有 1 的 R(a,b) 之和<= a,b <= n。
例如，如果 n = 2，则解为 R(1,1) + R(1,2) + R(2,1) + R(2,2) = 1 + 2 + 1 + 1 = 5。
由于有 n^2 对对应于要加在一起的数字，无论 R 的效率如何，简单地为每一对计算 R(a,b) 不会比 O(n^2) 好。因此，为了提高为了算法的效率，更快的方法必须以某种方式一次计算多个值的 R(a,b) 的总和。我怀疑有一些属性可能有用：
为什么这段代码会返回一个数字因子的总和？
在几个Project Euler问题中,您被要求计算因子的总和作为问题的一部分.在那里的一个论坛上,有人发布了以下Java代码作为查找总和的最佳方式,因为你实际上不需要找到个别因素,只需要找到主要因素(你不需要知道Java,你可以跳到下面的摘要):
public int sumOfDivisors(int n)
{
int prod=1;
for(int k=2;k*k<=n;k++){
int p=1;
while(n%k==0){
p=p*k+1;
n/=k;
}
prod*=p;
}
if(n>1)
prod*=1+n;
return prod;
}
现在,我已经尝试了很多次,我发现它有效.问题是,为什么？
说你因素100: 1,2,4,5,10,20,25,50,100.总和是217.主要因素分解是2*2*5*5.这个功能给你[5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217
保理8:1,2,4,8.总和是15.主要因素分解是2*2*2.这个功能给你[2*(2*(2+1)+1)+1]=15
该算法归结为(Fi用于表示因子F或F sub i的第i个索引):
return product(sum(Fi^k, k from 0 to Ni), i from 1 to m)
其中m,唯一素因子Ni的数量是每个唯一因子在素数因子分解中出现的次数.
为什么这个公式等于因子的总和？我的猜测是,它等于通过分配属性的每个独特的素因子组合(即每个独特因子)的总和,但我不知道如何.
我马上给出一个例子,现在假设我有3个数组a,b,c等
a = c(3,5)
b = c(6,1,8,7)
c = c(4,2,9)
我必须能够在它们之间提取连续的三元组,例如,
c(1,2,3),c(4,5,6)
但这仅仅是一个例子,我将拥有一个甚至超过10个数组的更大的数据集,因此必须能够找到连续的十个长度系列.
因此,任何人都可以提供算法,通常在'n'数组中找到连续的长度'n'系列.
我实际上在R中做这个东西,所以如果你用R代码你的代码它更可取.但是来自任何语言的算法都非常受欢迎.