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

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

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;
}