Big number MOD function.

(A*B) % MOD = ((A % MOD) * (B % MOD)) % MOD

So

(A^n) % MOD = (((A ^ (n/2)) % MOD) * ((A ^ (n/2)) % MOD)) % MOD;

function is:

int cal(int pow, int val, int MOD) {
    if(pow == 0)
        return 1;
    int v = cal(pow/2, val, MOD);
    if(pow % 2 == 0)
        return (v*v) % MOD;
    else
        return (((v*val) % MOD) * v) % MOD;
}

Best Sieve Technique

#include<iostream>
#include<cstdio>
#include<cmath>

int N = 5000, status[2501];
int main() {
    int i, j, sqrtN;
    for( i = 2; i <= N >> 1; i++ ) status[i] = 0;
    sqrtN = int( sqrt((double)N) ); // have to check primes up to (sqrt(N))
    for( i = 3; i <= sqrtN; i += 2 ) {
        if( status[i>>1] == 0 ) {
// so, i is a prime, so, discard all the multiples
// j = i * i, because it’s the first number to be colored
            for( j = i * i; j <= N; j += i + i )
                status[j>>1] = 1; // status of the multiple is 1
        }
    }
// print the primes
    printf("2 ");
    for( i = 3; i <= N; i += 2 ) {
        if( status[i>>1] == 0 )
            printf("%d ", i);
    }


}

by: Jane Alam Jan

Sieve of Eratosthenes

#include<iostream>
#include<cstdio>

int N=100000;
int status[100001];
int main(){
    int i,j;
    for(i=2; i<=N; i++) status[i]=0;
    for(i=3; i<=N; i+=2) {
        if(status[i] == 0) {
            for(j = 2* i; j<=N; j+=i) status[j] = 1;
        }
    }
    for( i=2; i<=N; i++) if(status[i]==0) printf("%d ", i);

    return 0;

}

Main Source : Jane Alam Jan

int N = 5000;int status[5001];// status[i] = 0, if i is prime
// status[i] = 1, if i is not a primeint main() {int i, j;// initially we think that all are primesfor( i = 2; i <= N; i++ )
status[i] = 0;for( i = 3; i <= N; i += 2 ) {if( status[i] == 0 ) {// so, i is a prime, so, discard all the multiples
// 3 * i is odd, since i is odd. And j += 2 * i, so, the next odd
// number which is multiple of i will be foundfor( j = 3 * i; j <= N; j += 2 * i )
status[j] = 1; // status of the multiple is 1}
}// print the primesprintf("2 ");for( i = 3; i <= N; i += 2 ) {if( status[i] == 0 ) {// so, i is primeprintf("%d ", i);
}
}return 0;
}  

File Management

code : how to read data from a file and write output in anther file


///Bis-millah-hir-rahmanir-rahim.
//arafat,sylhet engineering college,Bangladesh.

///****Love coding, love solving problems. --Coder shall be coder.******


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

#define pi acos(-1)
#define nl endl
#define sp " "
#define msa 200010
#define pf printf
#define sc scanf
#define pb push_back
#define pob pop_back

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);

    FILE *f,*f2; ///tow pointer for read and write
    int a,b,c;
    f = fopen("file.txt","r"); ///you must create a file(any name, here file.txt)
    f2 = fopen("out.txt", "w"); /// create another file or it will create itself (just rename the file here)
    fscanf(f,"%d %d",&a,&b); ///fscanf is a function for reading data from file
    c=a+b;
    fprintf(f2,"%d\n",c); /// fprintf is a function for writing data to a file
    fclose(f); /// close the input file
    fclose(f2); /// close the output file



    return 0;
}

Different uses of string class plus

string name;
getline (cin, name);
// read a whole line into the string name(works like ase gets() )

//swaping
string s1,s2;
cin>>s1>>s2;
swap(s1,s2);

//we could convert the first character of a string to upper case with the following code

string s= "hello";
s[0] = toupper(s[0]);

//we could use that method to control a loop that allows us to convert all the characters to upper case

for (string::size_type i = 0; i < str.length(); i++)
{
    str[i] = toupper (str[i]);
}

// for lowercase we can use tolower() function


to find posintion of a character or substring

string s;
cin>>s;
int p= s.find('a'); ///to find first occurence of a character or substring
int q= s.rfind('a'); ///to find last occurence of a character or substring
cout<<p;

to learn more

Different Uses of String class

C++ Standard Library: The string Class

The string class is part of the C++ standard library. A string represents a sequence of characters.
To use the string class, #include the header file:

#include <string>

Constructors:

• string ()
  - creates an empty string ("")
• string ( other_string )
  - creates a string identical to other_string
• string ( other_string, position, count )
  - creates a string that contains count characters from other_string, starting at position. If count is missing (only the first two arguments are given), all the characters from other_string, starting at position and going to the end of other_string, are included in the new string.
• string ( count, character )
  - create a string containing character repeated count times

Examples:

 string s1;                //   s1 = ""                

 string s2( "abcdef" );    //   s2 = "abcdef"          

 string s3( s2 );          //   s3 = "abcdef"          

 string s4( s2, 1 );       //   s4 = "bcdef"           

 string s5( s2, 3, 2 );    //   s5 = "de"              

 string s6( 10, '-' );     //   s6 = "----------"      

      

The string class also has a destructor that takes care of freeing the memory storing the characters when the object is destroyed.

Constant Member Functions:

These functions do not modify the string.

• const char * data ()
  - returns a C-style null-terminated string of characters representing the contents of the string
• unsigned int length ()
  - returns the length of the string
• unsigned int size ()
  - returns the length of the string (i.e., same as the length function)
• bool empty ()
  - returns true if the string is empty, false otherwise

Operators Defined for string:

• Assign =
string s1;
string s2;
...
s1 = s2; // the contents of s2 is copied to s1
• Append +=
string s1( "abc" );
string s2( "def" );
...
s1 += s2; // s1 = "abcdef" now
• Indexing []
string s( "def" );
char c = s[2]; // c = 'f' now
s[0] = s[1]; // s = "eef" now
• Concatenate +
string s1( "abc" );
string s2( "def" );
string s3;
...
s3 = s1 + s2; // s3 = "abcdef" now
• Equality ==
string s1( "abc" );
string s2( "def" );
string s3( "abc" );
...
bool flag1 = ( s1 == s2 ); // flag1 = false now
bool flag2 = ( s1 == s3 ); // flag2 = true now
• Inequality !=
  - the inverse of equality
• Comparison <, >, <=, >=
  - performs case-insensitive comparison
  string s1 = "abc";
string s2 = "ABC";
string s3 = "abcdef";
...
bool flag1 = ( s1 < s2 ); // flag1 = false now
bool flag2 = ( s2 < s3 ); // flag2 = true now

Member Functions:

• void swap ( other_string )
  - swaps the contents of this string with the contents of other_string.
  string s1( "abc" );
string s2( "def" );
s1.swap( s2 ); // s1 = "def", s2 = "abc" now 
  
• string & append ( other_string )
  - appends other_string to this string, and returns a reference to the result string.
  
• string & insert ( position, other_string )
  - inserts other_string into this string at the given position, and returns a reference to the result string.
  
• string & erase ( position, count )
  - removes count characters from this string, starting with the character at the given position. If count is ommitted (only one argument is given), the characters up to the end of the string are removed. If both position and count are omitted (no arguments are given), the string is cleared (it becomes the empty string). A reference to the result string is returned.
  
• unsigned int find ( other_string, position )
  - finds other_string inside this string and returns its position. If position is given, the search starts there in this string, otherwise it starts at the beginning of this string.
  
• string substr ( position, count )
  - returns the substring starting at position and of length count from this string
  

---

solution for n! in java using BigInteger Class

import java.util.Scanner;
import java.math.BigInteger;
class Main
{
// standard Java class name in UVa OJ
    public static void main(String[] args)
    {
        int n;
        Scanner sc= new Scanner(system.in);
        n=sc.nextInt;
        BigInteger fac = BigInteger.ONE;
        for (int i = 2; i <=n; i++)
            fac = fac.multiply(BigInteger.valueOf(i));
// it is in the library!
        System.out.println(fac);
    }
}

integer to string and string to integer

integer to string:

int a = 10;
stringstream ss;
ss << a;
string str = ss.str();

string to integer:

stringstream convert(p1);
convert>>v;
stringstream conver(p2);
conver>>v2;
cout<<v+v2<<nl;

June 2016 contest calender

Experimental Educational Round: VolBIT Formulas Blitz (J. Divisibility)

অস্থির একটা জিনিস

Let's factorize numbers from 2 to 10. 2 = 2, 3 = 3, 4 = 22, 5 = 5, 6 = 2·3, 7 = 7, 8 = 23, 9 = 32, 10 = 2·5. If a number is divisible by all numbers from 2 to 10, its factorization should contain 2 at least in the power of 3, 3 at least in the power of 2, 5 and 7 at least in the power of 1. So it can be written as x·23·32·5·7 = x·2520. So any number divisible by 2520 is divisible by all numbers from 2 to 10.

There are  numbers from 1 to n divisible by all numbers from 2 to 10. In a programming language it is usually implemented as simple integer division.

My Java Learning

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package my.first.java.program;

import java.math.BigInteger;
import java.util.Scanner;
import java.math.*;
/**
 *
 * @author A K Tamzid
 */
public class MyFirstJavaProgram {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
      BigInteger a,b,c;
     
      Scanner sc= new Scanner(System.in);
      a=sc.nextBigInteger();
      //b=sc.nextBigInteger();
      //a= new BigInteger("1");
      b= new BigInteger("2");
      c=a.mod(b);
      System.out.println(c);
      if(c==a)
          System.out.println("Yes");
       


    }
   
}

Uses of Pair

Pair : Simple Containers – The C++ Standard Template Library (STL)

Pair

The pair container is a simple container consisting of two data elements or objects. The first element is referenced as ‘first’ and the second element as ‘second’ and the order is fixed (first, second). Pair is used to combine together two values which may be different in type. Pair provides a way to store two heterogeneous objects as a single unit. Pair can be assigned, copied and compared. The array of objects allocated in a map or hash_map are of type ‘pair’ by default in which all the ‘first’ elements are unique keys associated with their ‘second’ value objects.

pair <int, char> g1;         //default pair <int, char> g2(1, 'a');  //initialized,  different type pair <int, int> g3(1, 10);   //initialized,  same type  pair <int, char> g4(g3);    //copy of g3

Another way to initialize a pair is by using the make_pair() function.

g2 = make_pair(1, 'a');

To access the elements, we use variable name followed by dot operator followed by the keyword first or second.

cout << g2.first << g2.second;

Here is a C++ program that shows how pair works.

#include <iostream> #include <utility>   //for pair #include <string>    //for string functions using namespace std; int main() {     pair <string, int> g1;     pair <string, int> g2("Quiz",  3);     pair <string, int> g3(g2);     pair <int, int> g4(5,  10);     g1 = make_pair(string("Geeks"), 1);     g2.first = ".com";     g2.second = 2;     cout << "This is pair g" << g1.second << " with the "          << "value " << g1.first << "." << endl << endl;     cout << "This is pair g" << g3.second          << " with the value " << g3.first          << ". This pair was initialized as a copy of "          << "pair g2." << endl << endl;     cout << "This is pair g" << g2.second          << " with the value " << g2.first          << ". The values of this pair were"          << " changed after initialization."          << endl << endl;     cout << "This is pair g4 with values "          << g4.first << " and " << g4.second          << " made for showing addition. The "          << "sum of the values in this pair is "          << g4.first+g4.second          << "." << endl << endl;     cout << "We can concatenate the values of"          << " the pairs g1,  g2 and g3 : "          << g1.first + g3.first + g2.first << endl << endl;     cout << "We can also swap pairs "          << "(but type of pairs should be same) : " << endl;     cout << "Before swapping, " << "g1 has " << g1.first          << " and g2 has " << g2.first << endl;     swap(g1, g2);     cout << "After swapping, "          << "g1 has " << g1.first << " and g2 has " << g2.first;     return 0; }