# Topcoder SRM 640 Div2 T3 TwoNumberGroupsEasy 题解

Topcoder Single Round Match 640 DIv2 T3 TwoNumberGroupsEasy 题解

（TC SRM 从 640 到 616 持续施工～）

## Translation

• A and B will each contain between 1 and 10 elements, inclusive.
• All elements of A will be distinct.
• All elements of B will be distinct.
• The number of elements in numA will be the same as the number of elements in A.
• The number of elements in numB will be the same as the number of elements in B.
• All elements of A and B will be between 1 and 1,000,000,000, inclusive.
• All elements of numA and numB will be between 1 and 100,000, inclusive.
• Time limit (s): 2.000
• Memory limit (MB): 256

## Examples

{1,2,3,4}
{2,1,1,1}
{5,6,7,8}
{1,1,1,2}

Returns: 2

This input describes the multisets A = {1,1,2,3,4} and B = {5,6,7,8,8}. For M=2, we have (A modulo M) = {0,0,1,1,1} and (B modulo M) = {0,0,0,1,1}. The distance between these two multisets is 2, and that is the best we can get.

{5,7}
{1,1}
{12,14}
{1,1}

Returns: 0

A 集合是 {5,7}，而 B 集合是 {12,14}，显然 M=7 时两个集合相同。

The optimal solution is obtained for M = 7.

## Original

A multiset is the same thing as a set, with the difference that a multiset can contain multiple copies of the same element. For example, {1,1,1,2,3} is a multiset that contains three 1s, one 2, and one 3.
The distance between two multisets is the smallest total number of elements we need to erase from them in order to make them equal. For example, the distance between {1,1,2,2,3} and {1,2,2,4} is 3. Note that we can compute distance as follows: For each value, we count its occurrences in the first multiset, we count its occurrences in the second multiset, and we write down the difference between those two counts. The distance is then equal to the sum of all values we wrote down.
If S is a multiset, then (S modulo M) is the multiset of all values (x modulo M) where x belongs to S. For example, if S = {11,12,13,21,22} and M = 10, then (S modulo M) = {1,2,3,1,2} = {1,1,2,2,3}.
You have two multisets called A and B. The first multiset is described by the vector s A and numA. For each valid i, the multiset contains numA[i] copies of the value A[i]. The second multiset is described by the vector s B and numB in the same way.
We are now looking for a positive integer M with the following properties: M must be greater than 1, and the distance between (A modulo M) and (B modulo M) must be as small as possible. Compute and return the smallest possible distance.

## Analysis

A_i\equiv B_j  \pmod m \iff A_i-B_j \equiv 0 \pmod m

## Code

#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
map<int,int> cnt;
map<int,int>::iterator it;
class TwoNumberGroupsEasy {
public:
int solve( vector <int> A, vector <int> numA, vector <int> B, vector <int> numB );
};
inline int MyAbs(int x){return x>0?x:-x;}
int TwoNumberGroupsEasy::solve(vector <int> A, vector <int> numA, vector <int> B, vector <int> numB) {
vec.clear();
for (int i=0;i<A.size();i++)
for (int j=0;j<B.size();j++){
int now=MyAbs(A[i]-B[j]);
for (int k=2;k<=sqrt(now);k++) if (now%k==0){
vec.push_back(k);
if (now/k!=now) vec.push_back(now/k);
}
vec.push_back(now);
}
vec.push_back(1<<30);
int ret=1<<30;
for (int i=0;i<vec.size();i++){
int m=vec[i];
cnt.clear();
if (m==0||m==1) continue;
int now=0;
for (int j=0;j<A.size();j++) cnt[A[j]%m]+=numA[j];
for (int j=0;j<B.size();j++) cnt[B[j]%m]-=numB[j];
for (it=cnt.begin();it!=cnt.end();it++) now+=MyAbs(it->second);
if (now<ret) ret=now;
}
return ret;
}

# Related posts

Topcoder SRM 639 Div2 T3 BoardFoldingDiv2 题解 