Connection Status:
Competition Arena > TwoNumberGroups

TwoNumberGroups

SRM 640 · 2014-08-25 · by dreamoon

SRM 640 · 2014-08-25 · by dreamoon · Math
Class Name: TwoNumberGroups
Return Type: int
Method Name: solve
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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
0)
{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.

1)
{100}
{2}
{1}
{1}
Returns: 28
2)
{5,1}
{1,1}
{12,999999894}
{1,1}
Returns: 202073
3)
{1}
{1}
{1}
{100000}
Returns: 0
4)
{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

Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TwoNumberGroups with a public method int solve(vector<int> A, vector<int> numA, vector<int> B, vector<int> numB) · 76 test cases · 2 s / 256 MB per case

Submitting as anonymous