Exact Sum

11057 Exact Sum


 Peter received money from his parents this week and wants to spend it all buying books. But he does not read a book so fast, because he likes to enjoy every single word while he is reading. In this way, it takes him a week to finish a book. As Peter receives money every two weeks, he decided to buy two books, then he can read them until receive more money. As he wishes to spend all the money, he should choose two books whose prices summed up are equal to the money that he has. It is a little bit difficult to find these books, so Peter asks your help to find them. Input Each test case starts with 2 ≤ N ≤ 10000, the number of available books.


Next line will have N integers, representing the price of each book, a book costs less than 1000001. Then there is another line with an integer M, representing how much money Peter has. There is a blank line after each test case. The input is terminated by end of file (EOF).

Output For each test case you must print the message:
 ‘Peter should buy books whose prices are i and j.’,
where i and j are the prices of the books whose sum is equal do M and i ≤ j. You can consider that is always possible to find a solution, if there are multiple solutions print the solution that minimizes the difference between the prices i and j.
 After each test case you must print a blank line
.
 Sample Input
2
40 40
 80

5
10 2 6 8 4
10

Sample Output
Peter should buy books whose prices are 40 and 40.
Peter should buy books whose prices are 4 and 6.


*************************************code*******************************
#include <iostream>
#include <algorithm>

using namespace std;

int books[10000];

int main()
{
    int N, M;
   
    while (cin >> N)
    {
        for (int i = 0; i < N; ++i)
            cin >> books[i];
       
        sort(books, books + N);
       
        cin >> M;
       
        int i = 0, j = N - 1;
        int bI, bJ;
        while (i < j)
        {
            if (books[i] + books[j] < M)
                ++i;
            else if (books[i] + books[j] == M)
            {
                bI = i;
                bJ = j;
                ++i; --j;
            }
            else
                --j;
        }
       
        cout << "Peter should buy books whose prices are " << books[bI] << " and " << books[bJ] << ".\n\n";
    }
}

Number of Factors

Alice has learnt factorization recently. Bob doesn't think she has learnt it properly and hence he has decided to quiz her. Bob gives Alice a very large number and asks her to find out the number of factors of that number. To make it a little easier for her, he represents the number as a product of N numbers. Alice is frightened of big numbers and hence is asking you for help. Your task is simple. Given N numbers, you need to tell the number of distinct factors of the product of these N numbers.

Input:

First line of input contains a single integer T, the number of test cases.

Each test starts with a line containing a single integer N.
The next line consists of N space separated integers (A_i).

Output:

For each test case, output on a separate line the total number of factors of the product of given numbers.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 10
2 ≤ Ai ≤ 1000000

Example:

Input:

3
3
3 5 7
3
2 4 6
2
5 5

Output:

8
10
3

Scoring:

You will be awarded 40 points for correctly solving for A_i ≤ 100.

You will be awarded another 30 points for correctly solving for A_i ≤ 10000.

The remaining 30 points will be awarded for correctly solving for A_i ≤ 1000000.

********************************************editorial**************************************************************

Problem:

You are given a very large number represented as a product of N numbers. Given this number representation, you need to find the number of distinct factors of the original number which is formed by the product of given N numbers.

Quick Explanation:

We can factorize each one of the N given numbers into its prime factors. Then we find the number of occurrences of each prime factor, say they are a1, a2,...aK, if we have K distinct prime factors. Our answer is simply: (a1+1)(a2+1)(...)*(aK+1).

Detailed Explanation:

This problem relies on some knowledge of divisor function. Divisor functions returns the number of positive and distinct divisors of a number. Let's call it d(x).

• Some properties of the divisor function:
  We now look into some important properties of the divisor function:
  For a prime number p, we have d(p) = 2, as there are only two numbers which divide a prime number:1 and itself.
  Now, it's a known fact that this function is multiplicative but not completely multiplicative. This means that if two numbers, say, a and b are there such that gcd(a, b) = 1, then the following holds:  d(a*b) = d(a)*d(b).

This allows us to deduce the important relationship, that is the key of solving this problem:

For a prime number, p, we have: d(p^n) = n+1.

Now, it's easy to understand that all we need to do is to factorize all the N given numbers into its prime factors, and, for each prime factor we also need to count how many times it appears (that is, we need to know the exponent of each prime factor).

Once we have this count with us (which can be done using integer factorization and for example, the set and map data structures, one to guarantee uniqueness of the factors and the other to save the number of occurences for each unique prime factor), all we need to do is to multiply all these numbers plus one together and we will obtain our answer.

As an example, consider the number:

504 = 2^3 * 3^2 * 7^1

The number of distinct divisors of 504 is then (3+1) * (2+1) * (1+1) = 24.

Applying this process to all numbers yields the answer to the problem :)

**************************************CODE***********************************************************************************

#include<iostream>

using namespace std;

 typedef  int lli;

 #include<bits/stdc++.h>

lli prime[1000000];

lli base[1000000];

 int read_int(){

char r;

bool start=false,neg=false;

int ret=0;

while(true){

r=getchar();

if((r-'0'<0 || r-'0'>9) && r!='-' && !start){

continue;

}

if((r-'0'<0 || r-'0'>9) && r!='-' && start){

break;

}

if(start)ret*=10;

start=true;

if(r=='-')neg=true;

else ret+=r-'0';

}

if(!neg)

return ret;

else

return -ret;

}

 int pri()

  {

  //cout<<" prime "<<endl;

   for(int i=2;i<1011;i++)

    {

     if(!prime[i])

       {

        for(  int j=2;j*i<=1000001;j++)

         {

         //  cout<<prime[i]<<" "<<j<<endl;

            prime[j*i]=1;

  }

}

 

}

// cout<<" here "<<endl;

 int pt=0;

 for(int i=2;i<1000001;i++)

  {

   if(!prime[i]) base[pt++]=i; 

  }

 //  cout<<" gone "<<endl;

return 0;

  }

  

  

 int fact(map<lli,lli> &mymap,lli num)

  {

  int kk=10;

  for(int i=0;;i++)

   {

   // if(kk--==0) return 0; 

    if(num==0 || num==1)return 0;

     else

      {

      lli div=base[i];

      //if(div==0) return 0;

      int k=10;

     

       while(num%div==0 && num!=0 && num!=1)

        {

       // if(k--==0) return 0;

        // cout<<num<<endl;

         mymap[div]++;

         num/=div;

         if(num==0) return 0;

 }

  }

}

  }

  

  

 int main()

  {

  pri();

   

  int t;

  // cin>>t;

  t=read_int();

   while(t--)

    {

     

    int n;

   // scanf("%d",&n);

   n=read_int();

     int arr[n];

      map<lli,lli> mymap;

      for(int i=0;i<n;i++)

       {

        int a;

          //scanf("%d",&a);

          a=read_int();

          fact(mymap,a);

           }

           map<lli,lli> ::iterator it;

            lli ans=1;

           for(it=mymap.begin();it!=mymap.end();it++)

            {

            //cout<<" falcul"<<ans<<endl;

            ans*=(it->second+1);

}

           

             cout<<ans<<endl;

             

   

  }

  return 0;

}