Programming Quest June 29, 2010

From YoungProgrammer.com

LCM-GCD based question

Question:

We all interested in mathematics and world are divided in to two parts.
One who are interested in mathematics and other who are afraid of mathematics.
Here is a equation:
( X * N ) % Y = 0

Given two number X & Y you have to find minimum N that satisfies the equation.

Input:

Input consists of two positive integer X & Y . (1<=X,Y<=2000000000)

Output:

You have to output minimum N.

Sample Input:

1 5
6 7

Sample Output:

5
7

Note: You have to give the total of all output for each input. 
For the sample input set, you have to give 
7+5 = 12. So answer is 12.

Download data sets

ANS-562252
my solution
#include<cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <sstream>
#include <iomanip>
#include <complex>
#include <queue>
#include <functional>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define last(a) int(a.size() - 1)
#define all(a) a.begin(), a.end()
#define seta(a,x) memset (a, x, sizeof (a))
#define I (int)
#define SZ(x) ((int) (x).size())
#define FE(i,x) for(typedef((x).begin() i=(x).begin();i!=(x).end();i++) 

typedef long long int  int64;
typedef unsigned long long int uint64;
typedef long double ldb;
typedef pair <int, int> pii;
typedef vector<int>vi;
typedef vector<string>vs;
 

 
template <class T> T sqr (T x) {return x * x;}

int gcd(int a,int b)
{
 if(b==0) return a;
 return gcd(b,a%b);
}

int main()
{
 int X,Y;
 int total=0;
 while(1)
 {
 cin>>X>>Y;
 int hcf=gcd(X,Y);
 int lcm=(X*Y)/hcf;
 total+=(lcm/X);
 cout<<total<<endl;
 }




return 0;
}

Programming Quest June 29, 2010

If a number is the only number between a prime number and a square number it is 
beprisque.
Such few numbers are: 2 3 8 10
2 is beprisque, because, 1 is a square and 3 is a prime number
3 is beprisque, because, 2 is prime and 4 is a square number
What's the 100th beprisque number ?

ANS-119026
From Young programmer.com

my solution (not optimized)

#include<cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <sstream>
#include <iomanip>
#include <complex>
#include <queue>
#include <functional>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define last(a) int(a.size() - 1)
#define all(a) a.begin(), a.end()
#define seta(a,x) memset (a, x, sizeof (a))
#define I (int)
#define SZ(x) ((int) (x).size())
#define FE(i,x) for(typedef((x).begin() i=(x).begin();i!=(x).end();i++) 

typedef long long int  int64;
typedef unsigned long long int uint64;
typedef long double ldb;
typedef pair <int, int> pii;
typedef vector<int>vi;
typedef vector<string>vs;
 

 
template <class T> T sqr (T x) {return x * x;}

int main()
{
 static int prime[1000009];
 static int sqr[1000009];
 for(int i=1;i<=1000;i++)
 sqr[i*i]=1;
 
 prime[1]=0;prime[2]=1;

 for(int i=3;i<=1000000;i=i+2)
 {
 int flag=1;
 for(int j=3;j<=sqrt(i);j++)
 {
 if(i%j==0) { flag=0;break;}
 else continue;
 }
 if(flag==1) prime[i]=1;
 }

 int count=0;
 for(int i=2;i<=120000;i++)
 {
 if((sqr[i-1]==1&&prime[i+1]==1)||(sqr[i+1]==1&&prime[i-1]==1)){cout<<i<<endl; ++count;}
 }

 cout<<count<<endl;
 


return 0;
}





here is  the few BEPRISQUE number
2
3
8
10
24
48
80
82
168
224
226
360
440
442
728
840
1088
1090
1224
1368
1522
1848
2026
2208
2400
3024
3250
3720
3968
4760
5040
5624
5928
6562
7920
8648
9802
10608
11026
11448
12322
13688
13690
14160
14640
15130
16128
17160
18224
19320
21024
21610
24024
25920
28560
29242
29928
31328
33488
36480
42024
44520
47088
47962
49728
50626
53360
54288
56168
56170
57120
59050
61008
62002
64008
65026
66048
67080
70224
71288
74528
74530
77840
81224
85848
88210
89400
90600
91808
91810
95480
95482
97968
99224
103042
104328
112224
113568
116280
119026
100

Programming Quest June 29, 2010

From Young Programmers site

Determine the number of n-bit sequences that contain no adjacent 1’s. For
example, for n = 3 the answer is 5 (sequences 000, 001, 010, 100, 101 are
acceptable while 011, 110, 111 are not).
Find the answer where n = 10

ANS-144

#include<cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <sstream>
#include <iomanip>
#include <complex>
#include <queue>
#include <functional>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define last(a) int(a.size() - 1)
#define all(a) a.begin(), a.end()
#define seta(a,x) memset (a, x, sizeof (a))
#define I (int)
#define SZ(x) ((int) (x).size())
#define FE(i,x) for(typedef((x).begin() i=(x).begin();i!=(x).end();i++) 

typedef long long int  int64;
typedef unsigned long long int uint64;
typedef long double ldb;
typedef pair <int, int> pii;
typedef vector<int>vi;
typedef vector<string>vs;
 

 
template <class T> T sqr (T x) {return x * x;}

int main()
{
 char s[1028];
 int count=0;
 for(int i=0;i<1024;i++)
 {
 int tmp=i;
 int j=0;
 if(i==0) {s[0]='0';s[1]='\0';}
 while(tmp>0)
 {
 int rem=tmp%2;
 s[j++]=rem+'0';
 tmp=tmp/2;
 }
 if(i!=0)
 s[j]='\0';
 //printf("%s\n",s);

 if(!strstr(s,"11")) ++count;   
 }

 cout<<count<<endl;

return 0;
}