The maximum possible product of digits among all integers from 1 to n.

In the first example the maximum product is achieved for 389$389$ (the product of digits is 3⋅8⋅9=216$3\cdot 8\cdot 9=216$).

In the second example the maximum product is achieved for 7$7$ (the product of digits is 7$7$).

In the third example the maximum product is achieved for 999999999$999999999$ (the product of digits is 99=387420489$9^9=387420489$).

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

#define fi(i,a,b)    for(long long i=a;i<=b;i++)
#define fr(i,a)      for(long long i=0;i<a;i++)
#define fd(i,a,b)    for(long long i=b;i>=a;i--)
#define clr(x)       memset(x,0,sizeof(x))
#define cln(x)       memset(x,-1,sizeof(x))
#define __           printf(" ")
#define _            printf("\n")
#define _o           printf("1\n")
#define stree        long long lft=node<<1,rht=(node<<1)|1,mid=(s+e)>>1
#define snode        long long s,long long e,long long node
#define slft         s,mid,lft
#define srht         mid+1,e,rht
#define sin()        if(S<=s&&e<=E)
#define sout()       if(S>e||s>E)
#define mod          1000000007
#define read()       freopen("in.txt","r",stdin)
#define write()      freopen("out.txt","w",stdout)
#define sfl(x)       scanf("%I64d",&x)
#define sfll(x,y)    scanf("%I64d %I64d",&x,&y)
#define sflll(x,y,z) scanf("%I64d %I64d %I64d",&x,&y,&z)
#define pfl(x)       printf("%I64d",x)
#define pfll(x,y)    printf("%I64d %I64d",x,y)
#define pflll(x,y,z) printf("%I64d %I64d %I64d",x,y,z)
#define xx           1000000

typedef long long ll;
typedef pair<long long,long long> pll;



main(){
    long long n;
    cin>>n;
    long long cur=1,ans=0,pre=1,v;
    string s;
    while(n){
        s+=(char(n%10)+'0');
        n/=10;
        cur*=9;
    }

    long long sz=s.size();sz--;

    //cout<<s<<" "<<cur<<endl;

    ans=cur/9;

    while(sz>=0){
        v=s[sz]-'0';
        cur/=9;
        ans=max(ans,max(pre*(v-1)*cur,pre*v));
        pre*=v;
        sz--;
    }
    cout<<ans<<endl;




    return 0;
}






Again


//#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#include<cstdio>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<queue>
#include<set>
#include<cmath>
#include<cstdlib>
#define pi                  acos(-1)
#define READ                freopen("in.txt", "r", stdin)
#define WRITE               freopen("out.txt", "w", stdout)
#define INF9                 1000000010
#define INF18               1000000000000000010
#define dist(ax,ay,bx,by)   sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))
#define mod                  1000000007
#define gcd(a,b)            __gcd(a,b)
#define lcm(a,b)            (a*b)/__gcd(a,b)
#define m_p(a,b)            make_pair(a,b)
#define pb                  push_back
#define bpll(a)             __builtin_popcountll(a)
#define MX                  100005

typedef long long lli;
typedef unsigned long long llu;
using namespace std;

vector<lli>ara;



lli func(lli idx, bool small)
{
//    cout<<idx<<endl;
    if(idx==ara.size()) return 1;

    lli ret=0;
    if(small)
    {
        ret= 9*func(idx+1, small);
    }
    else
    {
        ret=0;
        for(lli i=1; i<ara[idx]; i++)
        {
            ret= max(ret, i*func(idx+1, true));
        }
        ret= max(ret, ara[idx]*func(idx+1, small));
    }
    return ret;
}


int main()
{
    lli n;

    cin>>n;

    while(n)
    {
        lli rem= n%10;
        ara.push_back(rem);
        n/=10;
    }

    reverse(ara.begin(), ara.end());

    lli ans= func(0, false);
    ans= max(ans, func(1, true));
    cout<<ans<<endl;


    return 0;
}

UVA 10190- Divide, But Not Quite Conquer!

#include<stdio.h>
long d[200000002];
int main()
{
    long p,m;
    while(scanf("%ld%ld",&p,&m)!=EOF)
    {
        long n,c,j,k=0,s=0,q=0,l,count=0;
        l=p;
        if(p<2||m<2)
        {
            s=1;
        }
        else
        {
            for(k=0; p>1; k++)
            {
                if(p%m!=0)
                {
                    s=1;
                    break;
                }
                else
                {
                    count=count+1;
                    p=p/m;
                    d[k]=p;
                }
            }
        }
        if(s==1)
            printf("Boring!\n");
        else
        {
            printf("%ld",l);
            for(j=0; j<count; j++)
                printf(" %ld",d[j]);
            printf("\n");
        }
    }
    return 0;
}

Bitwise sieve

#include<bits/stdc++.h>
using namespace std;
#define M 100000000
bool check(long long N,long long pos)
{
    return (bool)(N&(1<<pos));
}
long long setit(long long N,long long pos)
{
    return N=(N|(1<<pos));
}
long long status[(M/32)+5],i,j;
vector<long long>vec;
void bit_sieve()
{
    for(i=3;i<=sqrt(M);i+=2)
    {
        if(check(status[i/32],i%32)==0)
        {
            for(j=i*i;j<=M;j+=i*2)
            {
                status[j/32]=setit(status[j/32],j%32);
            }
        }
    }
    vec.push_back(2);
    for(i=3;i<=M;i+=2)
    {
        if(check(status[i/32],i%32)==0)
        {
            vec.push_back(i);
        }
    }
}
main()
{
    bit_sieve();
    long long sz=vec.size();
    cout<<sz<<endl;
}

Light oj :- 1188 - Fast Queries( form i j, you have to find the number of distinct integers from index i to j)

Input

8 5

1 1 1 2 3 5 1 2

1 8

2 3

3 6

4 5

4 8

Output:

Case 1:

4

1

4

2

4

BY Segment tree:

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <complex>
#include <numeric>
#include <valarray>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
#define inf (1<<29)
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define nl printf("\n")
#define spc printf(" ")
#define sci(n) scanf("%ld",&n)
#define sc64(n) scanf("%I64d",&n)
#define scii(a,b) scanf("%ld %ld",&a,&b)
#define sc6464(a,b) scanf("%I64d %I64d",&a,&b)
#define scs(s) scanf("%s",s)
#define scss(a,b) scanf("%s %s",a,b)
#define scd(f) scanf("%lf",&f)
#define scdd(a,b) scanf("%lf %lf",&a,&b)
#define pfi(a) printf("%ld",a)
#define pf64(a) printf("%I64d",a)
#define pfii(a,b) printf("%ld %ld",a,b)
#define pf6464(a,b) printf("%I64d %I64d",a,b)
#define pfs(a) printf("%s",a)
#define pfss(a,b) printf("%s %s",a,b)
#define pfd(a) printf("%lf",a)
#define pfdd(a,b) printf("%lf %lf",a,b)
#define rep(i,n) for(int i(0),_n(n);i<_n;++i)
#define repr(i,n) for(int i=n;i>=0;i--)
#define repi(i,a,b) for(int i(a),_b(b);i<=_b;++i)
#define repl(i,n) for(int i(1),_n(n);i<=_n;++i)
#define repir(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mem(x,a) memset(x,a,sizeof(x))
#define repe(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
int dx[]={0,0,1,-1,1,-1,1,-1},dy[]={1,-1,0,0,1,-1,-1,1};
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#define ll long long
typedef vector<vector<int> > vvi;
#define MX 100060
long long tree[3*MX];
long long ar[MX],tr[3*MX],ss=0;
void  update(long l,long r,long i,long j,long node,long valu)
{
    if(i<=l&&j>=r)
    {
       tree[node]=valu;
        return;
    }
    if(i>r||j<l)
    return;

    long mid=(l+r)/2;

    long left=2*node;

    long right=left+1;

    update(l,mid,i,j,left,valu);

    update(mid+1,r,i,j,right,valu);

    tree[node]=tree[left]+tree[right];
}
void csum(long l,long r,long i,long j,long node)
{
    if(i<=l&&j>=r)
    {
        ss+=tree[node];
        return;
    }
    if(i>r||j<l)
    {
      return;
    }
    long mid=(l+r)/2;
    long left=2*node;
    long right=left+1;
    csum(l,mid,i,j,left);
    csum(mid+1,r,i,j,right);
}
int main()
{
    long n,q,a,b,pp;

    scanf("%ld",&pp);

    for(int ii=0;ii<pp;ii++)
    {
        scanf("%ld %ld",&n,&q);

    for(int i=1;i<=n;i++)
    scanf("%ld",&ar[i]);

    long s;

   vector<long>vc[100000],vt[100090];



    long aa[110000]={0},bb[100100]={0};

    for(int i=0;i<q;i++)
    {
        scanf("%ld%ld",&a,&b);

        vc[b].push_back(a);
        vt[b].push_back(i);

    }
    for(int i=1;i<=n;i++)
    {
       if(aa[ar[i]]!=0)
       {
           update(1,n,aa[ar[i]],aa[ar[i]],1,0);
       }

       update(1,n,i,i,1,1);
       //  for(int j=0;j<=15;j++)
       // cout<<tree[j]<<" ";
      // cout<<"\n";
       aa[ar[i]]=i;
       for(int j=0;j<vc[i].size();j++)
       {
           ss=0;
           csum(1,n,vc[i][j],i,1);
           //cout<<ss<<"\n";
           bb[vt[i][j]]=ss;
       }
    }
     printf("Case %ld:\n",ii+1);
    for(int i=0;i<q;i++)
    {
       printf("%ld\n",bb[i]);

    }
    }
return 0;
}


BY Binary indexed tree:


#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>

using namespace std;

#define sf scanf
#define pf printf

typedef map<int, int>mpii;

const int high = 100003;

struct Query
{
    int L , R , i;
}q[50007];

int ar[high] , ans[50007] , block=0 , answer=0 , mp[high];

bool cmp(Query x , Query y)
{
    if(x.L/block != y.L/block) return x.L/block < y.L/block;

    return x.R < y.R;
}

void add(int pos)
{
    mp[ar[pos]]++;

    if(mp[ar[pos]] == 1) answer++;
}

void rmoving(int pos)
{
    mp[ar[pos]]--;

    if(mp[ar[pos]] == 0) answer--;
}

void Results(int n , int m)
{
    block = (int)sqrt(n);

    sort(q , q+m , cmp);

    int i , currR = 0 , currL = 0 , L , R;

    for(i=0; i<m; i++)
    {
        L = q[i].L;
        R = q[i].R;

        while(currL < L)
        {
            rmoving(currL);
            currL++;
        }

        while(currL > L)
        {
            add(currL-1);
            currL--;
        }

        while(currR <= R)
        {
            add(currR);
            currR++;
        }

        while(currR > R+1)
        {
            rmoving(currR-1);
            currR--;
        }

        int indx = q[i].i;

        ans[indx] = answer;
    }
}

void solution(int m)
{
    for(int i=0; i<m; i++)
    {
        pf("%d\n" , ans[i]);
    }
}

int main()
{
    int t , tc=0 , n , i , qry , x , y;
    sf("%d", &t);
    while(t--)
    {
        memset(mp , 0 , sizeof mp);

        answer = 0;

        sf("%d %d", &n , &qry);

        for(i=0; i<n; i++)
        {
            sf("%d", &ar[i]);
        }

        for(i=0; i<qry; i++)
        {
            //sf("%d %d", &q[i].L , &q[i].R);

            scanf("%d", &x);
            scanf("%d", &y);
            x--;
            y--;
            q[i].L = x;
            q[i].R = y;
            q[i].i = i;

            q[i].i = i;
        }

        Results(n , qry);

        pf("Case %d:\n" , ++tc);

        solution(qry);
    }

    return 0;
}

1236 - Pairs Forming LCM (Important)

long long pairsFormLCM( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i; j <= n; j++ )
           if( lcm(i, j) == n ) res++; // lcm means least common multiple
    return res;
}


#include <bits/stdc++.h>
#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))
using namespace std;
#define maxx 10000007
bitset<maxx/2>vis;
vector<int>prime;

void sieve()
{
    int x=maxx/2, y=sqrt(maxx)/2;
    for(int i=1;i<=y;i++)
    {
        if(vis[i]==0)
        {
            for(int j=(i*(i+1)*2);j<x;j+=(2*i)+1)
                vis[j]=1;
        }
    }
    prime.pb(2);
    for(int i=3;i<maxx;i+=2)
        if(vis[i/2]==0)
        prime.pb(i);
}

int main()
{
    sieve();
    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll n;
        sfl(n);
        ll ans=1;
        ll root=sqrt(n);
        for(int i=0; i<SZ(prime) && prime[i]<=root;i++)
        {
            if(n%prime[i]==0)
            {
                int cnt=0;
                while(n%prime[i]==0)
                {
                    n/=prime[i];
                    cnt++;
                }
                ans*=(2*cnt+1);
                root=sqrt(n);
            }
        }
        if(n>1)
        {
            ans*=3;
        }
        PRINT_CASE;
        printf("%lld\n",(ans/2)+1);
    }

    return 0;
}

Harmonic number l8oj 1245

LIGHT OJ 1245


long long H( int n ) {
    long long res = 0;
    for( int i = 1; i <= n; i++ )
        res = res + n / i;
    return res;
}

limit n=2^31;



///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
int main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        ll n,nn,i,ans,n1;
        cin>>n;
        nn=n;
        ans=n;
        n1=n;
        for(i=2;i<=nn;i++)
        {
            nn=n/i;
            ans=ans+(n1-nn)*(i-1);
            if(nn>(i-1))
            {
                ans+=nn;
            }
            n1=nn;
        }
        printf("Case %ld: %lld\n",cs++,ans);
    }
    return 0;
}
/*
How about the following idea. Say n = 36. So, the result is.
36/1 + 36/2 + 36/3 + ... + 36/36
Now,
36/1 = 36
36/2 = 18
from these two parts we are sure that
36/36 = 1
36/18 = 2
So, 36/19 = 36/20 = 36/21 = ... = 36/36 = 1
So, 36/19 + 36/20 + ... + 36/36 = 36 - 18 = 18.
Again,
36/2 = 18
36/3 = 12
from these two parts we are sure that
36/18 = 2
36/12 = 3
So, 36/13 = 36/14 = ... = 36/18 = 2
So, 36/13 + 36/14 + ... + 36/18 = (18 - 12)*2
*/

Stable marriage CODE (Problem no:1400 LOJ)

#include<bits/stdc++.h>
#define fr(i,m) for(int i=0;i<m;i++)
using namespace std;
vector <int> woman[501];
vector <int> man[501];
int check[501];
int main()
{
    int N;
    scanf("%d",&N);
    int who,whom;
    queue <int> Circle;
    for(int i=1; i<=N; i++)
    {
        woman[i].clear();
        man[i].clear();
        check[i]=0;
        Circle.push(i);
    }
    for(int i=1; i<=N; i++)
    {
        scanf("%d",&who);
        for(int j=1; j<=N; j++)
        {
            scanf("%d",&whom);
            woman[who].push_back(whom);
        }

    }
    for(int i=1; i<=N; i++)
    {
        scanf("%d",&who);
        for(int j=1; j<=N; j++)
        {
            scanf("%d",&whom);
            man[who].push_back(whom);
        }
    }
    while(Circle.size()!=0)
    {
        int person=Circle.front();
        Circle.pop();
        for(int i=0; i<man[person].size(); i++)
        {
            int person_like=man[person][i];
            if(check[person_like]==0)
            {
                check[person_like]=person;//both are free
                break;
            }
            else
            {
                cout<<person<<"--> "<<person_like<<"\n";
                int flag=1;
                for(int j=0; j<woman[person_like].size(); j++)
                {
                    if(woman[person_like][j]==check[person_like])//woman likes her husband much
                        break;
                    else if(woman[person_like][j]==person)
                    {
                        Circle.push(check[person_like]);//making free her present husband
                        check[person_like]=person;//get married with new person
                        flag=0;
                    }
                }
                if(flag==0)
                    break;
            }
        }
    }
    for(int i=1; i<=N; i++)
        cout<<check[i]<<" "<<i<<"\n";
    return 0;
}

1400 NO

#include<bits/stdc++.h>

#define fr(i,m) for(int i=0;i<m;i++)

using namespace std;

vector <int> woman[501];

vector <int> man[501];

int check[501];

int main()

{

    int test,ll=1;

    scanf("%d",&test);

    while(test--)

    {

        int N;

        scanf("%d",&N);

        int who,whom;

        queue <int> Circle;

        for(int i=1; i<=N*2; i++)

        {

            woman[i].clear();

            man[i].clear();

            check[i]=0;

            Circle.push(i);

        }

        for(int i=1; i<=N; i++)

        {

            for(int j=1; j<=N; j++)

            {

                scanf("%d",&whom);

                man[i].push_back(whom);

            }

        }

        for(int i=1; i<=N; i++)

        {

            for(int j=1; j<=N; j++)

            {

                scanf("%d",&whom);

                woman[i+N].push_back(whom);

            }

        }

        while(Circle.size()!=0)

        {

            int person=Circle.front();

            Circle.pop();

            for(int i=0; i<man[person].size(); i++)

            {

                int person_like=man[person][i];

                if(check[person_like]==0)

                {

                    check[person_like]=person;

                    break;

                }

                else

                {

                    int flag=1;

                    for(int j=0; j<woman[person_like].size(); j++)

                    {

                        if(woman[person_like][j]==check[person_like])

                            break;

                        else if(woman[person_like][j]==person)

                        {

                            Circle.push(check[person_like]);

                            check[person_like]=person;

                            flag=0;

                        }

                    }

                    if(flag==0)

                        break;

                }

            }

        }

        printf("Case %d:",ll++);

        for(int i=N+1; i<=N*2; i++)

            printf(" (%d %d)",check[i],i);

        cout<<"\n";

    }

    return 0;

}