尋找一組數字的GCD？

所以，我在接受採訪時被問到了這個問題。給定一組數字（不一定是不同的），我必須找到給定數字組中所有可能子集的GCD的乘積。尋找一組數字的GCD？

我的做法，我告訴面試官：

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是這不會以最佳狀態工作大。我怎樣才能優化它？

來源

2015-10-11 rohansingh

你是什麼意思的「模數呢」？除數是什麼？ –

用你的3個步驟構建** a **子集。這應該如何找到**所有**子集？ – user463035818

另外，面試官可能想調整他們的術語。允許重複的無序列表通常稱爲「multiset」或「bag」。 –

假設每個數組元素在上述範圍內1..U一些U.

設f（x）爲子集與GCD數目的整數（X）。問題的解決方案就是所有不同因素的和的d^f（d）1 < = d < = U.

設g（x）是可被x整除的數組元素的數量。

我們有

f(x) = 2^g(x) - SUM(x | y, f(y))

我們可以（x）的在O（N * SQRT（U））通過枚舉每個數組元素的所有除數計算克。通過以直接的方式枚舉x的每個倍數，可以在O（U log U）中從高值到低值計算f（x）。

來源

2015-10-11 17:07:30

預 - 必要：

費馬小定理（有一個廣義的定理太），簡單的數學，模冪

說明：註釋：A []代表了我們輸入數組

顯然約束1 < = N < = 10^5，告訴我要麼你需要一個O（N * LOG N）解決方案，不要試圖認爲DP根據我的複雜性將是N * max（A [i ]）即約。 10^5 * 10^6。爲什麼？因爲你需要子集的GCD進行轉換。

好了，繼續前進

我們可以認爲泡吧用相同的GCD子集，使複雜的。

因此，讓迭代器i從10^6遞減到1，嘗試使用GCD設置我！

現在，使用GCD的子集（i），我可以將它與任何i * j相關聯，其中j是非負整數。爲什麼？

GCD（I，I * j）的=我

現在，

我們可以建立一個頻數表的任何元素的數量是相當到達！現在

，比賽我所做的就是期間保持亞羣的數量與F2 GCD（我）[我]

因此，我們做的是從j *的所有元素的總和頻率，其中J變化從1到floor（i/j）現在是具有公約數（而不是GCD）的子集，因爲i是（2^sum-1）。

現在我們必須從這個總和中減去GCD大於i的子集，並將i作爲gcd的公約數。

這也可以通過利用f2的總和相同的循環中完成的[I * j]的其中j從1變化到地板（I/J）

現在用GCD子集i等於2 ^總和-1 - f2的總和[ij]只需乘以i（GCD i次的子集數量）即power（i，2^sum -1 - f2 [ij]的和）。但是現在要計算這個指數部分可以溢出，但是您可以用MOD-1作爲MOD的首選！（費馬小定理）使用模冪運算

這是我的代碼片段，因爲我不確定我們現在可以發佈代碼！

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複雜的事情，我覺得我們可以不採取J = 1，做沒有F2，但它的好我還沒有想過這個問題，這是我怎麼設法得到AC。

來源

2015-10-14 16:02:37

尋找一組數字的GCD？

回答

相關問題