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;

}

Light oj 1059 solution

MST & BFS Combine
লাইট অজ ১০৫৯
এমনিতে মিনিমাম ডিসট্যান্স বের করে +কত গুলোর জন্য বি এফ এস আলাদা ভাবে চালান লাগছে সেইগুলোর সাথে   এইচ বার বার গুন
2
4 4 100
1 2 10
4 3 12
4 1 41
2 3 23

উত্তর আসছে ১০+১২+২৩+(১০০*১)=১৪৫
আউটপুট ঃ Case 1: 145 1

5 3 1000
1 2 20
4 5 40
3 2 30

উত্তর আসছে ঃ ২০+৪০+৩০+(১০০০*২)=২০৯০
আউটপুট ঃ Case 2: 2090 2




#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
struct edge
{
    int u,v,w;
    bool operator < ( const edge& p ) const
    {
        return w < p.w;
    }
};
int pr[100107],aa[100010];
long kk,f,g,h;
vector<edge>e;
int find(int r)
{
    return (pr[r]==r) ? r:  find(pr[r]);
}
int mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1; i<=n; i++)
        pr[i]=i;

    long long count=0,s=0;                                                                                                                                                           "Fuck\n";
    for(int i=0; i<(int)e.size(); i++)
    {
        int u=find(e[i].v);

        int v=find(e[i].u);

        if(u!=v)
        {
            pr[u]=v;
            count++;
            if(e[i].w>=h)
            {
                if(aa[v]==0)
                {
                    kk++;
                    aa[v]=1;
                }

                if(aa[u]==0)
                {
                    kk++;
                    aa[u]=1;
                }
            }
            else
                s+=e[i].w;
            if(count==n-1)
                break;
        }
    }
    return s;
}
vector<int>vc[100100];
long long ff[100008],l;
void bfs(int n)
{
    queue<int>q;

    q.push(n);

    while(!q.empty())
    {
        int u=q.front();

        ff[u]=1;

        if(aa[u]==1)
            l=1;

        for(int i=0; i<vc[u].size(); i++)
        {
            int v=vc[u][i];

            if(ff[v]==0)
            {
                ff[v]=1;

                q.push(v);
            }
        }
        q.pop();
    }
}
int main()
{
    long  m;

    cin>>m;

    fr(ii,m)
    {
        long long i,u,v,w,cc=0;
        kk=0;

        cin>>f>>g>>h;

        for(i=1; i<=g; i++)
        {
            cin>>u>>v>>w;

            edge get;

            get.u=u;
            get.v=v;
            get.w=w;

            e.push_back(get);

            vc[u].push_back(v);

            vc[v].push_back(u);
        }
        long xx=mst(f);

        for(i=1; i<=f; i++)
        {
            if(ff[i]==0)
            {
                l=0;
                bfs(i);
                //cout<<i<<" "<<l<<"\n";
                if(l==0)
                    cc++;
            }
        }

        printf("Case %ld: ",ii+1);
        cout<<xx+kk*h+cc*h<<" "<<kk+cc<<"\n";
        e.clear();
        fr(i,f+3)
        {
            aa[i]=0;
            vc[i].clear();
            ff[i]=0;

        }
    }
    return 0;

}

UVA 12428 - Enemy at the Gates

///...................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
main()
{
    timesave;
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,m;
        cin>>n>>m;
        long total=n-1;
        m-=(n-1);
        long k=1;
        while(m>0)
        {
            m-=k;
            if(k==1)
                total-=2;
            else
                total--;
            k++;
        }
        cout<<total<<endl;
    }
}

UVA 12425 - Best Friend

///...................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
vector<ll> prime;
char vis[1000100];
#define sz 1000000
void sieve()
{
    prime.push_back(2);
    ll sqrtn = sqrt(sz),i,j;
    for(i=3; i<=sqrtn; i+=2)
    {
        if(vis[i]==0)
        {
            for(j=i*i; j<=sz; j+=2*i)
                vis[j]=1;
        }
    }
    for(i=3; i<=sz; i+=2)
        if(vis[i]==0)
            prime.push_back(i);
}
vector<ll>vec,vec1,phi;
ll calc(ll nm)
{
    ll res=nm,i;
    ll sqrtn=sqrt(nm);
    for(i=0; i<prime.size()&&prime[i]<=sqrtn; i++)
    {
        if(nm%prime[i]==0)
        {
            while((nm%prime[i])==0)
            {
                nm/=prime[i];
            }
            res/=prime[i];
            res*=prime[i]-1;
        }
    }
    if(nm!=1)
    {
        res/=nm;
        res*=nm-1;
    }
    return res;
}
main()
{
    timesave;
    sieve();
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        ll n,q,i,sq;
        cin>>n>>q;
        vec.clear();
        vec1.clear();
        phi.clear();
        sq=sqrt(n);

        for(i=1; i<=sq; i++)
        {
            if(n%i==0)
            {
                vec.push_back(i);
                if(n/i!=i)
                {
                    vec.push_back(n/i);
                }
            }
        }
        sort(vec.begin(),vec.end());
        vec1.clear();
        for(i=0; i<vec.size(); i++)
        {
            phi.push_back(calc(n/vec[i]));
            if(i)
            {
                phi[i]+= phi[i-1];/// for comulative sum
            }
        }
        ll nm;
        printf("Case %ld\n",cs++);
        for(i=1; i<=q; i++)
        {
            cin>>nm;
            if(nm>=n)
            {
                printf ( "%lld\n", n );/// sob guloi answer
                continue;
            }
            if(nm<1)
            {
                printf ( "%lld\n", 0 );///kono tai ans hobe na
                continue;
            }
            ll pos =upper_bound(vec.begin(),vec.end(),nm )-vec.begin();
            pos--;
            printf ( "%lld\n", phi[pos] );
        }
    }
}

UVA 12791 - Lap

#include <cstdio>

int main()
{
  int X, Y;
  while (scanf("%d %d", &X, &Y) != EOF) {
    int d = Y - X;
    int lap = Y / d;
    if (Y % d)
      lap++;
    printf("%d\n", lap);
  }
  return 0;
}