找到一组数字的GCD？ [英] Finding GCD of a set of numbers?
问题描述
所以，有人问我在一次采访中这个问题。给定一组号码（不一定是不同的），我一定要找到GCD的给定的一组数字的所有可能的子集的乘法。
So, I was asked this question in an interview. Given a group of numbers (not necessarily distinct), I have to find the multiplication of GCD's of all possible subsets of the given group of numbers.
我的做法，我告诉面试官：
My approach which I told the interviewer:
1. Recursively generate all possible subsets of the given set.
2a. For a particular subset of the given set:
2b. Find GCD of that subset using the Euclid's Algorithm.
3. Multiply it in the answer being obtained.
假定的空集GCD为1。 但是，将有2的n次方的子集，这将无法工作最佳，如果n很大。如何优化呢？
Assume GCD of an empty set to be 1. However, there will be 2^n subsets and this won't work optimally if the n is large. How can I optimise it?
推荐答案
pre - 必要
费马小定理（有一个广义的定理太），简单的数学，模幂
Fermat's little theorem (there is a generalised theorem too) , simple maths , Modular exponentiation
说明：注释：A []表示我们的输入数组
Explanation : Notations : A[] stands for our input array
显然制约1＆LT; = N＆LT; = 10 ^ 5，告诉我，要么你需要一个O（N * log n）的解决方案，不尝试根据我将是N *最大认为DP作为它的复杂性（A [我]），即约。 10 ^ 5 * 10 ^ 6。为什么？因为你需要的子集的GCD转型做。
Clearly the constraints 1<=N<=10^5 , tell me that either you need a O(N * LOG N ) solution , dont try to think DP as its complexity according to me will be N * max(A[i]) i.e. approx. 10^5 * 10 ^ 6 . Why? because you need the GCD of the subsets to make a transition.
好了，在移动
我们可以认为杵具有相同的GCD的子集，从而使复杂的
We can think of clubbing the subsets with the same GCD so as to make the complexity.
因此，让递减的迭代器，我从10 ^ 6比1的努力使镶有GCD我！
So , lets decrement an iterator i from 10^6 to 1 trying to make the set with GCD i !
现在以与GCD（我）的子集，我能俱乐部与任何I *Ĵ其中j是一个非负整数。为什么呢？
Now to make the subset with GCD(i) I can club it with any i*j where j is a non negative Integer. Why ?
GCD（I，I * j）条= I
GCD(i , i*j ) = i
现在，
我们可以建立一个频数表的任何元素的数量是相当可达！
We can build a frequency table for any element as the number is quite reachable!
现在，在比赛期间我所做的就是，保持子集的数量与GCD（我）在f2 [I]
Now , during the contest what I did was , keep the number of subsets with gcd(i) at f2[i]
因此，我们做什么，从j *，其中J从1变化到地板上的所有元素的总和频率（I / J） 现在有一个共同的除数（而不是GCD）为我的子集。（2 ^总和 - 1）
hence what we do is sum frequency of all elements from j*i where j varies from 1 to floor(i/j) now the subsets with a common divisor(and not GCD) as i is (2^sum - 1) .
现在我们已经从这笔款项中减去亚群的GCD比我大的，并有我的GCD的公约数是我。
Now we have to subtract from this sum the subsets with GCD greater than i and having i as a common divisor of gcd as i.
此，也可以在同一循环中通过利用f2的总和进行[I * j]中，其中j从1变化到地板（ⅰ/ j）条
This can also be done within the same loop by taking summation of f2[i*j] where j varies from 1 to floor(i/j)
现在有GCD的子集i等于2 ^总和-1 - F2的总和[IJ]只要乘我（与GCD亚群无我倍）即电源（I，2 ^总和-1 - F2的总和[IJ]）。但现在计算这个指数部分可能溢出，但你可以把它用％给予MOD-1的MOD是黄金！ （费马小定理），采用模幂
Now the subsets with GCD i equal to 2^sum -1 - summation of f2[ij] Just multiply i ( No . of subsets with GCD i times ) i.e. power ( i , 2^sum -1 - summation of f2[ij] ) . But now to calculate this the exponent part can overflow but you can take its % with given MOD-1 as MOD was prime! (Fermat little theorem) using modular exponentiation
下面是我的code代码片段，因为我不能确定现在我们能张贴code！
Here is a snippet of my code as I am unsure that can we post the code now!
for(i=max_ele; i >= 1;--i)
{
to_add=F[i];
to_subtract = 0 ;
for(j=2 ;j*i <= max_ele;++j)
{
to_add+=F[j*i];
to_subtract+=F2[j*i];
to_subtract>=(MOD-1)?(to_subtract%=(MOD-1)):0;
}
subsets = (((power(2 , to_add , MOD-1) ) - 1) - to_subtract)%(MOD-1) ;
if(subsets<0)
subsets = (subsets%(MOD-1) +MOD-1)%(MOD-1);
ans = ans * power(i , subsets , MOD);
F2[i]= subsets;
ans %=MOD;
}
我觉得我已经用F2复杂的事情，我觉得我们可以不用F2，不采取J = 1，但它的好我还没有想过这个问题，这是我设法交流
I feel like I had complicated the things by using F2, I feel like we can do it without F2 by not taking j = 1. but it's okay I haven't thought about it and this is how I managed to get AC .
这篇关于找到一组数字的GCD？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
