Thursday, 29 October 2015

Dima and Lisa(div 2 D)

D. Dima and Lisa

Dima loves representing an odd number as the sum of multiple primes, and Lisa loves it when there are at most three primes. Help them to represent the given number as the sum of at most than three primes.
More formally, you are given an odd numer n. Find a set of numbers pi (1 ≤ i ≤ k), such that
  1. 1 ≤ k ≤ 3
  2. pi is a prime
The numbers pi do not necessarily have to be distinct. It is guaranteed that at least one possible solution exists.
Input
The single line contains an odd number n (3 ≤ n < 109).
Output
In the first line print k (1 ≤ k ≤ 3), showing how many numbers are in the representation you found.
In the second line print numbers pi in any order. If there are multiple possible solutions, you can print any of them.
Sample test(s)
input
27
output
3
5 11 11
Note
A prime is an integer strictly larger than one that is divisible only by one and by itself.
-------------------------------------------editorial-----------------------------------------------------------------------------
according to number theory , any odd no can be writen as a sum of 3 prime number 
also any even no can be writen as a sum of 2 prime numbers 
now for any give odd number we  set first no as 3 , so now no become a even no (since odd no -3=even number ) , now we need to find 2 prime numbers which can give sum= that even number ,

we can do it very easily , there is another very big observation that any even no can be writen as a sum of 2 prime no , and one  of the prime number must be <10004, soo we iterate for all prime number till 10004 , and find 3rd number , now check whether that 3rd no is prime no or not
since 3rd no can be large , so we  cant use seiv , so we need to check in sqrt(no) complexity ...
there are some special cases , till 7
-----------------------------------------------------------code--------------------------------------------------------------
#include<iostream>
typedef long long int lli;
#include<bits/stdc++.h>
using namespace std;
int prime[1000000];
int main()
 {
  prime[1]=1;
  prime[0]=1;
  for(int i=2;i<=1000000;i++)
   {
    if(!prime[i])
     for(int j=2;j*i<=1000000;j++)
      {
       prime[i*j]=1;
}
  }
  
  lli n;
   cin>>n;
   
if(n==5)
{
cout<<"1"<<endl;
 cout<<"5"<<endl;
 return 0;
}
if(n==3)
{
cout<<"1"<<endl;
cout<<"3"<<endl;
return 0;
}
if(n==7)
{
  cout<<"3"<<endl;
  cout<<"2 2 3"<<endl;
  return 0;
}
cout<<3<<endl;
  cout<<3<<" ";
   n-=3;
   for(int i=2;i<=100004;i++)
    {
      if(!prime[i])
       {
         //cout<<" checking "<<i<<endl;
         lli re=n-i;
          //cout<<" re "<<re<<endl;
          int loop=sqrt(re);
         //  cout<<" loop till "<<loop<<endl;
          int f=0;
          for(int j=2;j<=loop;j++)
           {
             if(re%j==0) 
 {
   //cout<<" fali for "<<j<<endl;
  f=1;
  break;
 }
}
if(f==0)
 {
   cout<<i<<" "<<re<<endl;
  return 0;  
  }
         
 }
   }
 }


Posted by at No comments:

Thursday, 15 October 2015

Rupsa and Equilateral Triangle (x^2=y^2-z^2)

Rupsa and Equilateral Triangle 


Rupsa really loves triangles. One day she came across an equilateral triangle having length of each side as an integer N. She started wondering if it was possible to transform the triangle keeping two sides fixed and alter the third side such that it still remains a triangle, but the altered side will have its length as an even integer, and the line drawn from the opposite vertex to the mid-point of the altered side is of integral length.
Since Rupsa is in a hurry to record a song for Chef as he really loves her songs, you must help her solve the problem as fast as possible.

Input

The first line of input contains an integer T denoting the number of test cases.
Each test-case contains a single integer N.

Output

For each test case, output "YES" if the triangle transformation is possible, otherwise "NO" (quotes for clarity only, do not output).

Constraints

  • 1 ≤ T ≤ 106
  • 1 ≤ N ≤ 5 x 106

Sub tasks

  • Subtask #1: 1 ≤ T ≤ 100, 1 ≤ N ≤ 104 (10 points)
  • Subtask #2: 1 ≤ T ≤ 104, 1 ≤ N ≤ 106 (30 points)
  • Subtask #3: Original Constraints (60 points)

Example

Input:
2
5
3

Output:
YES
NO

Explanation

  • In test case 1, make the length of any one side 6, and it will suffice.
-----------------------------------editorial---------------------------------------------------------------------------------------------------

Pre-requisites

Basic math

Problem

Given an equilateral triangle having length of each side as an integer N. Is it possible to alter one of its' sides such that the height drawn to the altered side has integral length and the altered side has an even integer length?

Explanation

Let's recall the formula for calculating of length of the height of an isosceles triangle. If the length of the height is h, the length of the altered side is b, then h = sqrt(N2-b2/4). Then, h2=N2-b2/4. Let's denote b/2 by c and, since bshould be even, c should be integer. Then, we get h2=N2-c2. This is the same as N2=h2+c2. According to the statement, h and c should be integer.
Now, the problem is: given an integer N. Find out, whether it is possible to represent N2 as a sum of two integer numbers' squares or not.

How to get 10 points

Let's iterate through possible values of h, there are O(N) possible values of h. Then, let's check, if N2-h2 is a square of an integer number.
The total complexity of such a solution is O(TN) and it is capable only of solving the first subtask.

How to get 100 points

It is a well known fact that N can be represented as a sum of two perfect squares if and only if N is dividible by a prime of the form (4k+1), where k is an integer number.
So, let's find all the prime numbers not exceeding the maximal value of N. Then, let's pick all the prime numbers that give 1 modulo 4 and for each of them, mark all the numbers that are divisible by them and doesn't exceed the maximal possible value of N (say, MAX_N).
It takes MAX_N/P operations to mark all the integers that are divisible by P. Let's estimate the total number of the operations that we will make.
Since not every number is a prime of the form (4k+1), we can safely assume that the total number of operations won't exceed ∑NP=1NP that won't exceed O(T+MAX_N log MAX_N).
This solution gets 100 points.

---------------------------------------------------code------------------------------------------------------------
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int lli;
  5.  
  6. #define test() int test_case;cin>>test_case;while(test_case--)
  7. #define fr(i,n) for(int i=0;i<n;i++)
  8. #define frr(i,a,n) for(int i=a;i<n;i++)
  9. #define sll(a) scanf("%lld",&a)
  10. #define sl(a) scanf("%ld",&a)
  11. #define si(a) scanf("%i",&a)
  12. #define sd(a) scanf("%ld",&a)
  13. #define sf(a) scanf("%f",&a)
  14. #define rn(a) return a
  15. #define pai pair<int,int>
  16. #define pal pair<li,li>
  17. #define pall pair<lli,lli>
  18. #define ff first
  19. #define ss second
  20. #define mod 1000000007
  21. #define mp make_pair
  22. #define pb push_back
  23. #define pll(a) printf("%lld\n",a)
  24. #define pl(a) printf("%lld\n",a)
  25. #define pi(a) printf("%d\n",a)
  26. #define pd(a) printf("%lf\n",a)
  27. #define pf(a) printf("%f\n",a)
  28. #define lc (start+end)/2
  29. #define rc lc+1
  30. int sval;
  31. bool pcheck[9000000];
  32. bool num[9000000];
  34. int main()
  35. {
  37. pcheck[2]=0;
  38. int maxi=6000000;
  39. for(int i=2;i<=maxi;i++)
  40. {
  41. if(!pcheck[i])
  42. {
  43. bool checker=false;
  44. if((i-1)%4==0)
  45. {
  46. checker=true;
  47. num[i]=1;
  48. }
  49. for(int j=2;i*j<=9000000;j++)
  50. {
  51. pcheck[i*j]=1;
  52. //cout<<i*j<<" ";
  53. num[i*j]=checker | num[i*j];
  54. }
  55. }
  56. }
  57. test()
  58. {
  59. int n;
  60. scanf("%d",&n);
  61. if(n==1)
  62. printf("NO\n");
  63. else if(num[n])
  64. {
  65. printf("YES\n");
  66. }
  67. else
  68. printf("NO\n");
  69. }
  71. return 0;
  72. }
Posted by at No comments:

Wednesday, 7 October 2015

Dima and Lisa

D. Dima and Lisa

Dima loves representing an odd number as the sum of multiple primes, and Lisa loves it when there are at most three primes. Help them to represent the given number as the sum of at most than three primes.
More formally, you are given an odd numer n. Find a set of numbers pi (1 ≤ i ≤ k), such that
  1. 1 ≤ k ≤ 3
  2. pi is a prime
The numbers pi do not necessarily have to be distinct. It is guaranteed that at least one possible solution exists.
Input
The single line contains an odd number n (3 ≤ n < 109).
Output
In the first line print k (1 ≤ k ≤ 3), showing how many numbers are in the representation you found.
In the second line print numbers pi in any order. If there are multiple possible solutions, you can print any of them.
Sample test(s)
input
27
output
3
5 11 11
Note
A prime is an integer strictly larger than one that is divisible only by one and by itself.
------------------------------------------------------EDITORIAL-------------------------------------------------------------
There is a fact that the distance between adjacent prime numbers isn't big. For n = 109 maximal distanse is 282. So let's find maximal prime p, such that p < n - 1 (we can just decrease n while it's not prime(we can check it in )). We know that n - p < 300. Now we have even (because n and p are odd) number n - p and we should divide it into a sum of two primes. As n - p < 300, we can just iterate over small primes P and check if P is prime and n - p - P is prime. You can check that there is a solution for all even numbers less than 300 by bruteforce.
--------------------------------------CODE---------------------------------------------------------------------------------------

#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

#define mn 100000000
vector<int> v;
bool pcheck(int num);
int main()
{

 
 int num;
 cin>>num;
 
 
  
  if(num==5)
  {
   cout<<"1"<<endl;
    cout<<"5"<<endl;
    return 0;
  }
 
  if(num==3)
  {
  
  cout<<"1"<<endl;
  cout<<"3"<<endl;
  return 0;
  }
   if(num==7)
  {
     cout<<"3"<<endl;
     cout<<"2 2 3"<<endl;
     return 0;
  }
   cout<<"3"<<endl;
   cout<<"3 ";
   num-=3;
   //cout<<pcheck(21)<<endl;
   for(int j=3;j<=num;j+=2)
   {
          if(pcheck(j)&pcheck(num-j))
          {
             cout<<j<<" "<<num-j<<endl;
             break;
       }
   }
   return 0;
}


bool pcheck(int num)
{
 if(num==0)
 return 0;
 
 if(num==1)
 return 0;
 if(num==3)
 return 1;
 
 if(num==2)
 return 1;
 
   for(int i=2;i<=sqrt(num);i++)
   {
       if(num%i==0)
       return 0;
   }
   return 1;
}
Posted by at No comments:
Subscribe to: Comments (Atom)