Ankur's Blog

let's start Code

Showing posts with label Math. Show all posts
Showing posts with label Math. Show all posts

Segmented Sieve

, , No comments

Segmented Sieve [ Number Theory ]

Zobayer Blog

Implementation 01:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
#define MAX 100009

typedef long long ll;

vector<int>primes;


void seiveOfEratosthenes()
{
  bool flag[MAX+1];

  for(int i = 0; i <= MAX; i++)
    flag[i] = true;
  primes.push_back(2);

  flag[0] = flag[1] = false;

  for(int i = 4; i <= MAX; i += 2) flag[i] = false;

    for(int i = 3; i <= MAX; i += 2){

      if(flag[i] == true){ // i is prime
        primes.push_back(i);
        for(int j = i+i; j <= MAX; j = j+i){
          flag[j] = false; // j is not prime
        }
      }
    }
}

 void segmentedSeive(ll L, ll R)
 {
  bool isPrime[R-L+1];
  for(int i = 0; i <= (R-L+1); i++)
    isPrime[i] = true;

  if(L == 1)isPrime[0] = false; 

  for(int i = 0; i < (int)primes.size() && primes[i]*primes[i] <= R; i++){
    ll curPrime = primes[i];
    ll base = curPrime * curPrime;
    if(base < L){
      base = ( (L+curPrime - 1)/curPrime)*curPrime;
    }

    for(ll j = base; j <= R; j += curPrime)
      isPrime[j - L] = false;
  }
  for(int i = 0; i <= R - L; i++){
    if(isPrime[i] == true)
      cout << L + i << endl;
  }
 } 


int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    double start_time = clock();
    seiveOfEratosthenes();
    ll L,R;
    cin >> L >> R;
    segmentedSeive(L,R);
    return 0;

    double end_time = clock();
   // printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}

Implementation 02:



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032

unsigned base[MAX/64], segment[RNG/64], primes[LEN];

#define sq(x) ((x)*(x));
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))

typedef long long ll;

//Generates all the necessary prime numbers and marks them in base.
void seive()
{
  unsigned i,j,k;
  for(i = 3; i < LMT; i += 2)
    if(!chkC(base, i))
      for(j = (i * i), k = (i << 1); j < MAX; j += k)
        setC(base, j);
      for(i = 3, j = 0; i < MAX; i += 2)
        if(!chkC(base, i))
          primes[j++] = i;
}

// Returns the prime-count within range [a,b] and marks them in sement.
 int segmentedSeive(int a, int b)
 {
  unsigned i,j,k, cnt = (a <= 2 && 2 <= b) ? 1 : 0;
  if(b < 2) return 0;
  if(a < 3) a = 3;
  if(a%2 == 0)a++;
  mset(segment,0);
  for(i = 0; ( primes[i] * primes[i] ) <= b; i++){
    j = primes[i] * ((a + primes[i] - 1) / primes[i]);
    if(j%2 == 0) j += primes[i];
    for(k = (primes[i] << 1); j <= b; j += k)
      if(j != primes[i])
        setC(segment, (j-a));
  }
  for(i = 0; i <= (b - a); i += 2)
    if(!chkC(segment, i)){
      cnt++;
    }
    return cnt;
 } 


int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    double start_time = clock();
    seive();
    int L,R;
    cin >> L >> R;
    cout << segmentedSeive(L,R)<<endl;
    return 0;

    double end_time = clock();
   // printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}

Share:
Read More

12461 - Airplane

, , , No comments

12461 - Airplane

EXPLANATION

Solution:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include<bits/stdc++.h>
using namespace std;

int main()
{
int n;
while(cin >> n && n){
cout << "1/2\n";
}
return 0;
}

Share:
Read More

Euler’s Phi Function

, , No comments

Euler’s Phi Function:

Concept:  

Shoshikkha 

প্রোগ্রামিং পাতা 

topH 

 Type 01:

( যখন একসাথে অনেক গুলোর জন্য বের করতে হবে।)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
#define MAX 2000100

typedef long long ll;
ll phi[MAX];

void seivePHI(){
  ll i,j;
  for(i = 2; i < MAX; i++){
    if(phi[i] == 0){
      phi[i] = i - 1;
      for(j = i*2; j < MAX; j += i){
        if(phi[j] == 0)phi[j] = j;
        phi[j] /= i;
        phi[j] *= (i-1);
      }
    }
  }
}

int main()
{
   /* #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    double start_time = clock();*/

    int t;
    seivePHI();
    cin >> t;
    for(int cs = 1; cs <= t; cs++){
     int n;
     cin >> n;
     cout << "Phi("<<n<<") = "<<phi[n]<<endl;
    }


    /*double end_time = clock();
  printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
    */
    return 0;
}

Type 02:

( যখন  একটা সংখ্যার জন্য বের করতে হবে।)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 #include<bits/stdc++.h>
using namespace std;
#define MAX 2000100

typedef long long ll;

ll po(ll x, ll y){
  ll ans = 1;
  while(y--) ans *= x;
  return ans;
}

ll prime(ll a)
{
  for(ll i = 1; i*i <= a; i++){
    if(a%i == 0)return 1;
  }
  return 0;
}

ll phi(ll n)
{
  ll i,mul = 1, holder, fre = 0;
  if(prime(n) == 0) mul = n - 1;
  else{
    for(i = 2; i*i <= n; i++){
      if(n%i == 0){
        while(n%i == 0){
          n = n/i;
          holder = i;
          fre++;
        }
        mul *= (po(holder, fre-1)*(holder - 1));
        fre = 0;
      }
    }
    if(n != 1){
      mul *= (n-1);
    }
  }
  return mul;
}

int main()
{
   // #ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 // #endif
    //double start_time = clock();

       ll n;
     cin >> n;
     cout << "Phi("<<n<<") = "<<phi(n)<<endl;


    //double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
  
    return 0;
}

  Problems: D. Same GCDs   Solution


Share:
Read More

Count Divisors

, No comments

Count Divisors

Solution 1:

Complexity: sqrt(n)

#include<bits/stdc++.h>

using namespace std;


int countDivisors (int n)

{

    int cnt = 0;

    for(int i = 1; i <= sqrt(n); i++){

        if(n % i == 0){

            if(n/i == i)cnt++;

            else cnt += 2;

        }

    }

    return cnt;

}


int main()

{

    int n;

    while(cin >> n && n){

        cout << countDivisors(n)<<endl;

    }

    return 0;

}

Solution 2:

Complexity: O(n^1/3)

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

void Sieve(int n, bool prime[], bool primesqure[], int a[])
{
    for(int i = 2; i <= n; i++)
        prime[i] = true;

    for(int i = 0; i <= (n*n + 1); i++)
        primesqure[i] = false;

    prime[1] = false;
    for(int p = 2; p*p <= n; p++){
        if(prime[p] == true){
            for(int i = p*2; i <= n; i += p)
                prime[i] = false;
        }
    }
    int j = 0;
    for(int p = 2; p <= n; p++){
        if(prime[p])
        {
            a[j] = p;
            primesqure[p*p] = true;
            j++;
        }
    }
}

int countDivisors(int n)
{
    if(n == 1)return 1;

    bool prime[n+1], primesqure[n*n +1];
    int a[n];

    Sieve(n,prime, primesqure, a);

    int ans = 1;
    for(int i = 0; ; i++){
        if(a[i]*a[i]*a[i] > n)break;

        int cnt = 1;
        while(n % a[i] == 0){
            n = n/a[i];
            cnt = cnt + 1;
        }
        ans = ans * cnt;
    }

    if(prime[n])ans = ans * 2;
    else if(primesqure[n])ans = ans*3;
    else if(n != 1)ans = ans*4;
    return ans;
}
int main()
{
    int n;
    while(cin >> n && n){
        cout << countDivisors(n)<<endl;
    }
    return 0;
}

Share:
Read More

Large Number Factorial

, No comments

>> Large Number Factorial:


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 10000000
#define MAX 500


int multiply(int x, int res[], int res_size);

void factorial(int n)
{
    int res[MAX];

    res[0] = 1;
    int res_size = 1;

    for(int x = 2; x <= n; x++){
        res_size = multiply(x, res, res_size);
    }
    //cout << "factorial of Given NUmber is \n";
    for(int i = res_size - 1; i >= 0; i--)
        cout << res[i];
    cout << endl;
}

int multiply(int x, int res[], int res_size)
{
    int carry = 0;
    for(int i = 0; i < res_size; i++){
        int prod = res[i]*x + carry;
        res[i] = prod % 10;
        carry = prod/10;
    }

    while(carry){
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}

int main()
{
    FastIO;
  #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif

    int n;
    cin >> n;
    while(n--){
        int n;
        cin >> n;
        factorial(n);
    }
    return 0;
}
Share:
Read More

About

let's start CODE

Popular Posts

  • E-maxx training part - 01
                             Binary Exponentiation 1230 - MODEX              Solution 11029 - Leading and Trailing      Solution I...
  • 11029 - Leading and Trailing
    11029 - Leading and Trailing  Topic: Binary Exponentiation  
  • A - Frog 1
    A - Frog 1 Solution 01: IH19980412 //copy 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2...