শনিবার, ৩১ ডিসেম্বর, ২০১৬

UVA 10407 - Simple division

#include <stdio.h>
#include <math.h>
#include<bits/stdc++.h>
using namespace std;
main()
{
    while(1)
    {
        {
            long long  cnt=0,cnt1=0,diff,ans=0,i,a,ar[1010]={0},mn=10000000,i1,flag=0;
            while(cin>>a)
            {
                if(a==0&&cnt==0)
                {
                    flag=1;
                  break;
                }
                if(a==0&&cnt>0)
                    break;
                else
                {
                    ar[cnt]=a;
                    cnt++;
                }
            }
            if(flag==0)
            {
                for(i=1;i<cnt;i++)
                {
                    diff=ar[i]-ar[i-1];
                    ans=__gcd(ans,diff);
                }
                if(ans>=0)
                    cout<<ans<<endl;
                else
                    cout<<abs(ans)<<endl;
            }
            else
                break;
        }
    }
}

শুক্রবার, ৩০ ডিসেম্বর, ২০১৬

UVA 10311 - Goldbach and Euler

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

#define SIZE 100000001

char  status[SIZE]={0};
void sieve()
{
 long int i,j;
 int sq = sqrt(SIZE);
 for(i=3;i<=sq;i+=2)
   {
       {
            for(j=i*i;j<=SIZE;j+=2*i)
                status[j]=1;
       }
   }
   status[1]=1;
   status[0]=1;
   for(i=1;i<=SIZE;i++)
   {
       if(i%2==0&&i!=2)
       {
           status[i]=1;
           continue;
       }
   }

}

int main()
{
 unsigned long long int n;
 sieve();
 while(scanf("%llu",&n)==1)
 {
     unsigned long long i1,k1,flag=0,m;
     if(n%2==1)
     {
         if(n==1)
            printf("%llu is not the sum of two primes!\n",n);
         else if(status[n-2]==1)
         {
             printf("%llu is not the sum of two primes!\n",n);
         }
         else
             printf("%llu is the sum of 2 and %llu.\n",n,n-2);
     }
     else
     {
         m=0,flag=0;
         for(i1=n/2;i1<n;i1++)
         {
             if(status[(n/2)-m]==0 && status[i1]==0 && ((n/2)-m)!=i1)
             {
                 flag=1;
                 printf("%llu is the sum of %llu and %llu.\n",n,n-i1,i1);
                 break;
             }
             m++;
         }
     if(flag==0)
            printf("%llu is not the sum of two primes!\n",n);
     }
 }

}

বৃহস্পতিবার, ২৯ ডিসেম্বর, ২০১৬

UVA 897 - Anagrammatic Primes

#include <stdio.h>
#include <math.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<bits/stdc++.h>
using namespace std;

#define SIZE 40
long long int status[SIZE]={0},ar[50]={0};
 long long int i,j;
void sieve()
{
 int i,j;
 for(i=0;i<SIZE;i++) status[i]= 0;
 int sq = sqrt(SIZE);
 for(i=4;i<=SIZE;i+=2) status[i] = 1;
 for(i=3;i<=sq;i+=2)
   {
      if(status[i]==0)
       {
            for(j=2*i;j<=SIZE;j+=i)
             status[j]=1;
       }
   }
 status[1] = 1;
}
int main()
{
    sieve();
    long long n;
    while(cin>>n)
    {
        long long k1;
        if(n==0)
            break;
        else
        {
            if(status[n]==0)
            {
                 if(n==11 || n==23 || n==29)
                    {
                        cout<<"Given number is prime. But, NO perfect number is available." << endl;
                    }
                else
                {
                    k1=(pow(2,(n-1))+.00000000001)*((pow(2,n)+.00000000001)-1);
                    printf("Perfect: %lld!\n",k1);
                }
            }
            else
            {
                printf("Given number is NOT prime! NO perfect number is available.\n");
            }
        }
    }
}

বুধবার, ২৮ ডিসেম্বর, ২০১৬

UVA 897 - Anagrammatic Primes

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdlib>
#define N 10000001
using namespace std;

vector<long int>prime;

bool arr[N];
void sieve()
{
    long int k=sqrt(N);
    for(int i=3; i<=k; i+=2)
    {
        if(arr[i]==0)
        {
            for(long int j=i*i; j<N; j+=2*i)
            {
                arr[j]=1;
            }
        }
    }
    arr[1]=1;
    for(long int i=4; i<N; i+=2)
    {
        arr[i]=1;
    }

    prime.push_back(2);

    for(long int i=3; i<N; i+=2)
    {
        if(arr[i]==0)
        {
            prime.push_back(i);
        }
    }
}
int main()
{
    sieve();
    char str[10], *pEnd;
    long int num,limit,cnt,num1,loop,brk;
    while(gets(str))
    {
        long int len=strlen(str);
        if(str[0]=='0')
            break;
        if(len>=4)// 991 is the last Anagrammatic prime
        {
            printf("0\n");
            continue;
        }
        num=strtol(str,&pEnd,10);

        limit=1;
        for(long int j=1; j<=len; j++)
            limit*=10;
        //printf("   limit %ld\n",limit);

        brk=0;
        for(long int i=num+1; i<limit; i++)
        {
            if(arr[i]==0)
            {
                sprintf(str,"%ld",i);
                cnt=loop=0;

                sort(str,str+len);
                do
                {
                    num1=strtol(str,&pEnd,10);
                    if(arr[num1]==0)
                        cnt++;
                    loop++;
                }
                while(next_permutation(str,str+len));
                if(cnt==loop)
                {
                    brk++;
                    printf("%ld\n",i);
                    break;
                }
            }

        }
        if(brk==0)
            printf("0\n");
        memset(str,'\0',sizeof(str));
    }
    return 0;
}

UVA 10650 - Determinate Prime

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

#define SIZE 33001
long long int status[SIZE],ar[10000]={0},k=0;;

void sieve()
{
 long long int i,j;
 for(i=0;i<SIZE;i++) status[i]= 0;
 int sq = sqrt(SIZE);
 for(i=4;i<=SIZE;i+=2) status[i] = 1;
 for(i=3;i<=sq;i+=2)
   {
      if(status[i]==0)
       {
            for(j=2*i;j<=SIZE;j+=i)
             status[j]=1;
       }
   }

 status[1] = 1;
 status[0] = 1;
 for(i=0;i<=SIZE;i++)
 {
     if(status[i]==0)
     {
         ar[k]=i;
         k++;
     }
 }
}

int main()
{
 long long int n,i2;
 map<long long,long long>mp;
 sieve();
 long long a,b;
 while(cin>>a>>b)
 {
     long long i1,flag=0,i2,k1=0,diff=0,diff1=0,cnt=0,visit[32000]={0};
     if(a>b)
        swap(a,b);
     if(a==0&&b==0)
     {
         break;
     }
     else
     {
         i2=0;
         for(i1=0;i1<k;i1=i2+1)
         {
             i2=i1;
             if(ar[i1]<a)
                continue;
             if(ar[i1]>b)
                break;
             else
             {
                 if(ar[i1+1]<=b)
                 {
                     diff=ar[i1+1]-ar[i1];
                     if(ar[i1]-ar[i1-1]==diff)
                     {
                         //i2=i1+1;
                         continue;
                     }
                     else
                     {
                         if(ar[i1+2]<=b)
                         {
                             if(diff==(ar[i1+2]-ar[i1+1]))
                                {
                                    if(ar[i1+3]>b)
                                    {
                                        if(diff==(ar[i1]-ar[i1-1]))
                                            continue;
                                        else if(diff==(ar[i1+3]-ar[i1+2]))
                                                continue;
                                        else
                                        {
                                            cnt++;
                                            cout<<ar[i1]<<" "<<ar[i1+1]<<" "<<ar[i1+2]<<endl;
                                        }
                                    }
                                    else
                                    {
                                        if(diff==(ar[i1+3]-ar[i1+2]))
                                        {
                                            cnt++;
                                           cout<<ar[i1]<<" "<<ar[i1+1]<<" "<<ar[i1+2]<<" "<<ar[i1+3]<<endl;
                                        }
                                        else if(diff==(ar[i1]-ar[i1-1]))
                                            continue;
                                         else
                                        {
                                            cnt++;
                                            cout<<ar[i1]<<" "<<ar[i1+1]<<" "<<ar[i1+2]<<endl;
                                        }
                                    }
                                }
                             else
                                continue;
                         }
                     }
                 }
                 else
                    break;
             }
         }
     }
 }
}

সোমবার, ২৬ ডিসেম্বর, ২০১৬

UVA 446 - Kibbles "n" Bits "n" Bits "n" Bits

#include<bits/stdc++.h>
using namespace std;
main()
{
    long long ts;
    cin>>ts;
    while(ts--)
    {
        string s,s1,s3;
        char c;
        long long i,k=0,k1=0,ar[100]={0},ar1[100]={0},sum=0,sum1=0,ans,pow1=0,k2=0;
        cin>>s>>c>>s1;
        for(i=s.size()-1;i>=0;i--)
        {
            if(s[i]>='0'&&s[i]<='9')
            {
                k=s[i]-48;
                sum=sum+k*(pow(16,(pow1))+.0000000000001);
            }
            else
            {
                k=s[i]-55;
                sum=sum+k*(pow(16,(pow1))+.0000000000001);
            }
            pow1++;
        }
        pow1=0;
        for(i=s1.size()-1;i>=0;i--)
        {
            if(s1[i]>='0'&&s1[i]<='9')
            {
                k=s1[i]-48;
                sum1=sum1+k*(pow(16,(pow1))+.0000000000001);
            }
            else
            {
                k=s1[i]-55;
                sum1=sum1+k*(pow(16,(pow1))+.0000000000001);
            }
            pow1++;
        }

        if(c=='+')
        {
            ans=sum+sum1;
        }
        else if(c=='-')
        {
            ans=sum-sum1;
        }
        while(sum!=0)
        {
            ar[k2]=sum%2;
            sum/=2;
            k2++;
        }
        while(sum1!=0)
        {
            ar1[k1]=sum1%2;
            sum1/=2;
            k1++;
        }
        for(i=0;i<(13-k2);i++)
        {
            cout<<0;
        }
        for(i=k2-1;i>=0;i--)
        {
            cout<<ar[i];
        }
        printf(" %c ",c);
        for(i=0;i<(13-k1);i++)
        {
            cout<<0;
        }
        for(i=k1-1;i>=0;i--)
        {
            cout<<ar1[i];
        }
        cout<<" = ";
        cout<<ans<<endl;
    }
}

UVA 343 - What Base Is This?

#include<bits/stdc++.h>
using namespace std;
main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        long long l1,l2,i1,i2,i,pow1=0,flag=0,flag1=0,k,sum1=0,sum2=0,f=0;
        l1=s1.size();
        l2=s2.size();
        for(i1=2;i1<=36;i1++)
        {
            for(i2=2;i2<=36;i2++)
            {
                pow1=0;
                flag=0,flag1=0;
                sum1=0,sum2=0;
                for(i=l1-1;i>=0;i--)
                {
                    if(s1[i]>='0'&&s1[i]<='9')
                    {
                        k=s1[i]-48;
                    }
                    else
                        k=s1[i]-55;
                        if(k>=i1)
                            flag=1;
                        sum1=sum1+k*(pow(i1,pow1++)+.000000000001);
                }
                pow1=0;
                for(i=l2-1;i>=0;i--)
                {
                    if(s2[i]>='0'&&s2[i]<='9')
                    {
                        k=s2[i]-48;
                    }
                    else
                        k=s2[i]-55;
                        if(k>=i2)
                            flag=1;
                        sum2=sum2+k*(pow(i2,pow1++)+.000000000001);
                }
                if(flag==1)
                    continue;
                if(sum1==sum2)
                {
                    flag1=1;

                    break;
                }
            }
            if(flag1==1)
            {
                break;
            }
        }
        if(sum1==sum2)
        {
            cout<<s1;
                    printf(" (base %lld) = ",i1);
                    cout<<s2;
                           printf(" (base %lld)\n",i2);
        }
        else
        {
        cout<<s1;
        printf(" is not equal to ");
        cout<<s2;
        printf(" in any base 2..36\n");
        }
    }
}

UVA 355 - The Bases Are Loaded

#include<bits/stdc++.h>
using namespace std;
main()
{
    long long n,m;
    string s;
    while(cin>>n>>m>>s)
    {
        long long i,k=0,sum=0,pow1=0,flag=0,k1=0,k2=0;
       string ar;
        if(s[0]=='0')
            printf("0 base %lld = 0 base %lld\n",n,m);
        else
        {
            pow1=0;
            long  l=s.size();
            for(i=l-1;i>=0;i--)
                {
                    if(s[i]>='0'&&s[i]<='9')
                    k=s[i]-48;
                    else
                    k=s[i]-55;
                    if(k>=n)
                        flag=1;
                    sum=sum+(k*(pow(n,pow1++)+.00000000000001));
                }
                k1=0;

                if(sum==0)
                    ar[0]=0;
                while(sum!=0)
                {
                    k2=sum%m;
                    if(k2>9)
                    {
                        ar[k1]=char(k2+55);
                    }
                    else
                         ar[k1]=char (k2+48);
                    sum/=m;
                    k1++;
                }
                if(flag==1)
               cout<<s<<" is an illegal base "<<n<<" number"<<endl;
                else
                {
                    cout<<s;
                    printf(" base %lld = ",n);
                    for(i=k1-1;i>=0;i--)
                    {
                        cout<<ar[i];
                    }
                    printf(" base %lld\n",m);
                }
        }
    }
}

রবিবার, ২৫ ডিসেম্বর, ২০১৬

UVA 12043 - Divisors

#include<bits/stdc++.h>
using namespace std;
#define SIZE 100010
long long i,j,div1[SIZE];
long long  ddd[SIZE];
void check()
{
    for(i=1;i<=100000;i++)
    {
        for(j=i;j<=100000;j+=i)
        {
            div1[j]+=i;
            ddd[j]++;
        }
    }
}
main()
{
  check();
    long ts;
    cin>>ts;
    while(ts--)
    {
        long long a,b,c,ans=0,ans1=0,i1;
        cin>>a>>b>>c;
        for(i1=a;i1<=b;i1++)
        {
            if(i1%c==0)
            {
                ans1+=ddd[i1];
                ans+=div1[i1];
            }
        }
        cout<<ans1<<" "<<ans<<endl;
    }
}

Topic wise problem(number theory)

Prime problem uva : 406,543,686,897,914,10852,10650,10490,10394,10311,10168
GCD/LCM Problems uva : 408,412,106,10407,11388,11417,11774,12068
Factorial problems uva :324,568,623,10220,10323,10338
Prime factor Problems uva :516,583,10392,11466 ,160,993,10139,10622,10680,10780,10791,11395,11889
Big Mod /Inverse mod problems uva : 10090,10104,10633,10637 ,374,10212,11029
Fibonacci Numbers Problems uva : 495,900,948,1258,10183,10334,10450,10497,10597,11000,11089,11161,11780
Base Number Conversion problems Uva : 290,343,355,389,446,10473,10551

Number theory codeforces link :
https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=number+theory

Number Theory : https://a2oj.com/category?ID=41

Sorting problem : https://a2oj.com/category?ID=95

Big Mod /Inverse mod : http://www2.seas.gwu.edu/~poorvi/Classes/CS124_2006/CS124_InversePractice.pdf
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4664
https://www.codechef.com/tags/problems/inverse
https://www.codechef.com/tags/problems/modulo

বৃহস্পতিবার, ২২ ডিসেম্বর, ২০১৬

UVA-914 - Jumping Champion

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

#define SIZE 1000001

long long ar[1000010]={0}, status[SIZE],k=0;
 vector<long int>prime;
void sieve()
{
 int i,j;
 for(i=0;i<SIZE;i++) status[i]= 0;
 int sq = sqrt(SIZE);
 status[1] = 1,status[0] = 1;

 for(i=3;i<=sq;i+=2)
   {
      if(status[i]==0)
       {
            for(j=2*i;j<=SIZE;j+=i)
             status[j]=1;
       }
   }
   for(i=2;i<=SIZE;i++)
   {
       if(i%2==0&&i!=2)
       {
           continue;
       }
       else
       {
           if(status[i]==0)
           {
               prime.push_back(i);
           }
       }
   }
   k=prime.size();
}

int main()
{

 sieve();
 long long ts;
 cin>>ts;
 while(ts--)
 {
      long long int n,m,ans,mx=0,cnt=0,i1,vs,differ[200]={0},k1=0,low=0,high=0,k2=0;
      cin>>n>>m;
      for(i1=0;i1<k;i1++)
      {
          if(prime[i1]>=n&&cnt==0)
          {
              low=i1;
              cnt++;
          }
          else if(prime[i1]<=m)
          {
              high=i1;
          }
      }
     if(cnt!=0)
      {
          for(i1=low+1;i1<=high;i1++)
          {
              k1=prime[i1]-prime [i1-1];
              differ[k1]++;
          }
          for(i1=0;i1<=120;i1++)
          {
              if(differ[i1]>differ[k2])
              {
                  k2=i1;
              }
          }
          sort(differ,differ+120);
          if(differ[118]==differ[119])
          {
              printf("No jumping champion\n");
          }
          else
            printf("The jumping champion is %lld\n",k2);
      }
    else
      {
          printf("No jumping champion\n");
      }
 }
}

বৃহস্পতিবার, ১৫ ডিসেম্বর, ২০১৬

UVA 12068 - Harmonic Mean

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    else return gcd(b,a%b);
}
main()
{
    long long n,cs=1;
    cin>>n;
    while(n--)
    {
        long long n1,ar[100010]={0},i,lcm=1;
        cin>>n1;
        for(i=0;i<n1;i++)
        {
            cin>>ar[i];
            lcm=lcm*ar[i];
        }
        long long sum=0;
        for(i=0;i<n1;i++)
        {
            sum=sum+(lcm/ar[i]);
        }
        long long upper=lcm*n1;
        long long  lower=sum,vag=gcd(upper,lower);
        upper=upper/vag;
        lower=lower/vag;
        printf("Case %lld: ",cs++);
        cout<<upper<<"/"<<lower<<endl;
    }
}

মঙ্গলবার, ১৩ ডিসেম্বর, ২০১৬

UVA 884 - Factorial Factors

#include<bits/stdc++.h>
using namespace std;
#define mx 1000002
long long visit[mx]={0},ans[mx]={0},ar[mx]={0};

long long seive(long long n1)
{
    long long i,j,i1;
   for(i=3;i*i<=n1;i+=2)
   {
       if(visit[i]==0)
       for(j=i*i;j<=n1;j+=(2*i))
       {
           visit[j]=1;
       }
   }
   ar[2]=1;
   ans[2]=1;
   for(i=3;i<=n1;i++)
   {
       if(i%2==0)
       {
           ar[i]=ar[i/2]+1;
           ans[i]=ans[i-1]+ar[i];
       }
       else if(visit[i]==0)
       {
           ar[i]=1;
           ans[i]=ans[i-1]+ar[i];
       }
       else
       {
           for(i1=3;i1<=sqrt(i);i1+=2)
           {
               if(i%i1==0)
               {
                  ar[i]=ar[i1]+ar[i/i1];
                  ans[i]=ans[i-1]+ar[i];
                  break;
               }
           }
       }
   }
}
main()
{
    long long n;
    seive(1000000);
    while(cin>>n)
    {
        cout<<ans[n]<<endl;
    }
}

Factory Pattern

Factory Method  is a creational design pattern that provides an interface for creating objects in a superclass but allows subclasses to alte...