TwoNumberGroups | Topcoder Archive

Problem Statement

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.

You have two multisets called A and B. The first multiset is described by the int[]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 int[]s B and numB in the same way.

For a positive integer n, let f(n) be the sum of distinct prime factors of n. For example, f(12)=5 because the only primes that divide 12 are 2 and 3, and 2+3 = 5. Note that f(1)=0. Additionally, we define that f(0)=0 and that for any negative integer n we have f(n)=f(-n). For example, f(-1)=0 and f(-12)=5.

For each x in A and for each y in B we computed the value f(x-y). Return the sum of all those values, modulo 1,000,000,007.

Definition

Class:: TwoNumberGroups
Method:: solve
Parameters:: int[], int[], int[], int[]
Returns:: int
Method signature:: int solve(int[] A, int[] numA, int[] B, int[] numB)
(be sure your method is public)

Constraints

A and B will each contain between 1 and 1,000 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.

Examples

```
{1}
```
```
{2}
```
```
{3,7}
```
```
{1,1}
```
```
Returns: 14
```
This input describes the multisets A = {1,1} and B = {3,7}. For these two multisets we computed the following four values: f(1-3), f(1-3), f(1-7), and f(1-7). Their sum is f(2)+f(2)+f(6)+f(6) = 2+2+5+5 = 14.
```
{100}
```
```
{2}
```
```
{1}
```
```
{1}
```
```
Returns: 28
```

{5,1}

{1,1}

{12,999999894}

{1,1}

Returns: 202073

```
{1}
```
```
{1}
```
```
{1}
```
```
{100000}
```
```
Returns: 0
```

{11795180,41472124,44285836,84280940,117000811,150317409,154188370,167804776,225797581,
 240995620,301931440,306528163,327332717,333523124,341325123,350292524,400857064,401290197,
 426573408,427972026,448467719,563926065,574489831,579516358,609409829,659343788,678481187,
 775710113,806992032,831437250,839580344,842388073,869876247,899553191,902366903,975081878}

{1188,1769,1782,1757,1527,4958,3083,4439,3621,3958,2655,2250,2079,3885,3598,
 3236,3035,2286,7340,4127,3126,2904,2592,3082,3789,2776,3907,2368,4005,4863,
 4482,3307,2459,1436,1656,2007}

{11795180,41472124,44285836,84280940,117000811,150317409,154188370,167804776,225797581,240995620,
 301931440,306528163,327332717,333523124,341325123,350292524,400857064,401290197,426573408,
 427972026,448467719,563926065,574489831,579516358,609409829,659343788,678481187,775710113,
 806992032,831437250,839580344,842388073,869876247,899553191,902366903,942362007,975081878}

{3024,902,798,2,1426,4959,3082,4439,3622,3958,2653,2249,2081,3884,3599,
 3237,3033,2285,7340,4125,3127,2904,2592,3082,3789,2775,3907,2369,4006,
 4863,4483,3307,623,2303,2642,1757,2107}

Returns: 601548244

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.