-1

n整数の配列a0, a1, .. anと正の整数が与えられkます。(i,j)とが( は) でi+j割り切れるペアの数を見つけて出力します。この問題はhereから取得されました。ki+j % k == 0

時間内に解決策が必要O(n)です。

説明は、mod k に応じて要素をバケットに分けることでこれを行うことができるということです。たとえば、次の要素があります。1 3 2 6 4 5 9 and k = 3

mod 3 == 0 : 3 6 9
mod 3 == 1 : 1 4
mod 3 == 2 : 2 5

すると、次のように言われます。

これで、次のようにペアを作成できます: mod 3 == 0 の要素は (3 - 0) mod k = 0 の要素と一致するため、mod 3 == 0 リスト内の他の要素は次のようになります: (3, 6 ) (3, 9) (6, 9)

さらに遠く：

このようなペアは n * (n - 1) / 2 個あります。ここで、n はリストの長さです。これは、リストが同じであり、i != j であるためです。mod 3 == 1 の要素は (3 - 1) mod k = 2 の要素と一致するため、mod 3 == 2 リストの要素は次のようになります: (1, 2) (1, 5) (4, 2) ) (4, 5)

(3, 6) (3, 9) (6, 9) ( all items in the 0th bucket be paired)それ以来、それは理にかなってい(a + b)% k = 0 = a % k + b % kます。

明確でないのは、1 番目 (mod 3 == 1) および 2 番目 (mod 3 == 2) バケットの要素の組み合わせによって他のペアがどのように生成されたか、および n * (n - 1) / 2 ペアが存在する理由です。 . 別の（より良い）方法はありますか？

この質問は、質問を投稿する前に存在を知らなかった Math Stackexchange に適しています。

4

3 に答える 3

2

私はCコードを翻訳します...

using namespace std;
int main(){

   int n;
   int k;
   cin >> n >> k;
   int a[n];
   int m[k];
   for(int i=0; i<k; i++)
       m[i]=0;
    for(int i = 0; i < n; i++){
       cin >> a[i];
        m[a[i]%k]++;
    }
    int sum=0;
    sum+=(m[0]*(m[0]-1))/2;
     for(int i=1; i<=k/2 && i!=k-i; i++){
         sum+=m[i]*m[k-i];
     }
    if(k%2==0)
        sum+=(m[k/2]*(m[k/2]-1))/2;
    cout<<sum;
    return 0;
}

Python に:

def divisible_sum_pairs(n, k, a_list):
    m = [0] * len(a_list)
    for a in a_list:
        m[a % k] += 1

    sum = int(m[0] * (m[0] - 1) / 2)
    for i in range(1, int(k / 2) + 1):
        if i != k - 1:
            sum += m[i] * m[k - i]
    if k % 2 == 0:
        sum += m[int(k / 2)] * (m[int(k / 2)] - 1) / 2

    return sum

と：

print(divisible_sum_pairs(6, 3, [1,  3,  2,  6,  1,  2]))

あなたは5を得る

于 2016-07-15T13:48:41.137 に答える
1

n * (n - 1) / 2全員 ( n) は他の全員 ( ) とペアにできるため、ペアがありますn-1。ただし、順序は問題ではないため、ミラー ペアを 2 で割って数えるのを避けます。

また、分子を合計すると、同じ商を超える剰余が合計されますが、リマインダーは商を超えることはできません。3による除算のリマインダーは3、実際には のリマインダーです0。

答えは非常に巧妙です。おそらく、低レベルの最適化で数パーセント高速化できます。たとえば、の一般的なアルゴリズムに依存するのではなく、専用の module-by-3 を実装します%。O(n)しかし、すべての要素を少なくとも 1 回はスキャンする必要があり、ソリューションはすでにそれ以上のことを行っていないため、本当に勝つことはできません。（実際、結果を書くように求められているので、それだけでそれ以上のことはできないように思えますO(n^2)...）

これらの質問はいずれも Python とは関係ありません。math.stackexchange.comがあることをご存知ですか?

于 2016-07-15T13:36:46.543 に答える