DIV-Divisors

Divisors

Given below code is for div spoj or divisors spoj .

Hint:- very basic Sieve implementation .

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 21 October 2015 (Wednesday) 09:46
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
bool check[1009];
vector<int> prime;
void shieve()
{
    for(int i=3;i*i<=1000;i+=2)
    {
        if(!check[i])
        {
            for(int j=i*i;j<=1000 ; j+=i)
                check[j]=1;
        }
    }
    prime.pb(2);
    int j=1;
    for(int i=3;i<=1000;i+=2)
    {
        if(!check[i]){
            prime.pb(i);
        }
    }
}
bool isPrime(int n){
    if(n == 1)
        return false;
    for(int i = 2 ; i*i <= n ; i++){
        if(n%i == 0)
            return false;
    }
    return true;
}
int main()
{
    shieve();
    int ma = -1;
    int pos = 0;
    for(int i=1;i<=1000000;i++)
    {
        int temp=i;
        int total=1;
        int k=0;
        for(int j=prime[k]; k < prime.size() && j*j<=temp;j=prime[++k])
        {
            int count=0;
            while(temp%j==0)
            {
                count++;
                temp/=j;
            }
            total *=count+1;
        }
        if(temp!=1)
            total*=2;
        k = 0;
        for(int j = prime[k] ;k<prime.size() &&  j*j <= total ; j = prime[++k]){
            if(total%j == 0){
                int x = total / j;
                if(x!= j && isPrime(x)){
                    pos++;
                    if(pos%9 == 0)
                        printf("%d\n", i);
                    break;
                }
            }
        }
    }
    return 0;
} 

PRIME1-Prime Generator,PRINT-prime interval

Prime Generator

Below given code is for prime1 spoj or prime generator spoj .

This code will run for PRINT - prime intervals also . 

#include <bits/stdc++.h>
using namespace std;
vector<int > prime;
bool check[50009];
int keep = 1;
void pre()
{
    check[1 ] = 1;
    for(int i = 3 ; i <=224 ; i+=2){
        if(!check[i]){
            for(int j = i*i ; j<= 50000 ; j+=2*i)
                check[j] = true;
        }
    }
    prime.push_back(2);
    keep=1;
    for(int i = 3 ; i<= 50000 ; i++)
        if(check[i] == false && (i&1))
            prime.push_back(i) , keep++;
}
bool seg[1000009];
int main()
{
    int t;
    scanf("%d",&t);
    pre();
    while(t--)
    {
        int a , b;
        scanf("%d%d",&a , &b);
        if(b <= 50000){
            if(a<=2)
                printf("2\n");
            for(int i = a ; i<= b ; i++){
                if(check[i] == false && (i&1))
                    printf("%d\n", i);
            }
            continue;
        }
        memset(seg , 0 , sizeof seg);
        for(int i = 0; prime[i]*prime[i] <= b ; i++)
        {
            int begin = a/prime[i];
            begin *= prime[i];
            for(int j = begin ; j<= b ; j+= prime[i]){
                if(j < a)
                    continue;
                seg[j - a] = true;
            }
        }
        for(int i  = 0 ; prime[i]*prime[i] <= b ; i++){
            if(prime[i]>= a && prime[i]<=b)
                printf("%d\n",prime[i]);
        }
        for(int i = a==1?1:0 ; i < b-a+1 ; i++)
            if(seg[i]==0)
                printf("%d\n", i+a);
    }
    return 0;
}

FINDPRM-Finding Primes

Finding Primes

given below code is for findprm or finding primes spoj .

Here I have applied basic sieve to find primes . Here you have to tell the numbers of prime between N/2 and N . because all primes before N/2 are not common with second sieve(stated in question).

#include <bits/stdc++.h>
using namespace std;
bool primes[10000009];
int cum[10000009];
void pre(){
    for(int i = 3 ; i<= 3163 ; i+=2){
        if(!primes[i]){
            for(int j = i*i ; j<= 10000000 ; j+=2*i)
                primes[j] = 1;
        }
    }
    cum[2] = 1;
    for(int i = 3 ; i<=10000000 ; i++){
        if(primes[i] == 0 && i%2 != 0)
            cum[i] += cum[i-1] + 1;
        else
            cum[i] = cum[i-1];
    }
}
int main(){
    int t;
    pre();
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%d\n" , cum[n] - cum[(n>>1)]);
    }
    return 0;
}

OPSL-Operation Searchlight

Operation Searchlight

Given below c++ code is for OPSL spoj or Operation Searchlight spoj .

This is an easy problem & should be in tutorial class , here you should know sieve and how to calculate LCM of numbers.

PPATH-Prime Path

 Prime Path

Below given code is for PPATH spoj or Prime path spoj.

Hint:- Use BFS and sieve.

#include <bits/stdc++.h>
using namespace std;
bool check[10009];
void sieve()
{
    for(int i=2;i<=100;i++)
    {
        if(!check[i])
        {
            for(int j=i*i;j<=10000;j+=i)
                check[j] = true;
        }
    }
}
int conv_num(int a[])
{
    int temp=0,k=0;
    while(k<4){
        temp = temp*10 + a[k];
        k++;
    }
    return temp;
}
void arr(int a[],int num)
{
    int w=3;
    while(num)
    {
        a[w--] = num%10;
        num/=10;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    sieve();
    while(t--)
    {
        int digit[4],dist[10009],a,b,parent[10009];
        scanf("%d%d",&a,&b);
        memset(dist,-1,sizeof(dist));
        memset(parent,-1,sizeof(parent));
        queue<int> q;
        dist[a]=0;
        q.push(a);
        parent[a]=0;
        while(!q.empty())
        {
            int num = q.front();
            for(int k=3;k>=0;k--)
            {
                arr(digit,num);
                for(int i=0;i<=9;i++)
                {
                    digit[k] = i;
                    int temp = conv_num(digit);
                    if((!check[temp]) && dist[temp]==-1 && temp>=1000)
                    {
                        dist[temp]= dist[num] + 1;
                        parent[temp]=num;
                        q.push(temp);
                    }
                }
            }
            q.pop();
        }
        dist[b]==-1 ? cout<<"Impossible"<<endl : cout<<dist[b]<<endl;
    }
    return 0;
}

NDIV-n-divisors

n-divisors

Below given code is for NDIV spoj or n-divisors spoj;

Here basic idea is apply simple sieve and check for all the prime factors in the range of a to b .

#include <bits/stdc++.h>
using namespace std;
int check[32000];
int prime[10000];
void shieve()
{
    for(int i=3;i<=180;i+=2)
    {
        if(!check[i])
        {
            for(int j=i*i;j<=32000;j+=i)
                check[j]=1;
        }
    }
    prime[0] = 2;
    int j=1;
    for(int i=3;i<=32000;i+=2)
    {
        if(!check[i]){
            prime[j++]=i;
        }
    }
}
int main()
{
    shieve();
    int a,b,n,temp,total=1,res=0;
    scanf("%d%d%d",&a,&b,&n);
    int count=0,i,j,k;
    for(i=a;i<=b;i++)
    {
        temp=i;
        total=1;
        k=0;
        for(j=prime[k];j*j<=temp;j=prime[++k])
        {
            count=0;
            while(temp%j==0)
            {
                count++;
                temp/=j;
            }
            total *=count+1;
        }
        if(temp!=1)
            total*=2;
        if(total==n)
            res++;
    }
    printf("%d\n",res);
    return 0;
}

HABLU-Hablu and Bablu

Hablu and Bablu

Below given c++ code is for hablu spoj or Hablu and Bablu spoj

Here in the question given a number "N" and "K" PRIMES or "1" now we have to find the total number of divisor of "N" which are not divisible by any given PRIME .

If one is present in array then it will divide any number so here our final answer will became "0"

1- > Now if one is not present and then rest will be all prime.So we start diving number "N" by given primes till the number is not divisible by that prime this process removes all prime "P" present in the number .

After above process we will do the prime factorization of  "N"(remains after first process) 

If the prime factorization is as follow :->

N = p1^a  * p2^b * p3^c * .......*pn^k;

then total number of divisor will be

total = (a+1)*(b+1)*(c+1) .......*(k+1);

So here our total answer will be total number of divisor of "N"(remains after first process).

If you still have problem you can mail me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
#define LL long long
bool a[1000009];
LL prime[80000];
int total;
void pre()
{
    for(int i=2;i<=1000;i++)
    {
        if(!a[i])
            for(int j=i*i;j<=1000000;j+=i)
                a[j]=true;
    }
    total=0;
    prime[total++]=2;
    for(int i=3;i<=1000000;i+=2)
        if(!a[i])
            prime[total++]=i;
}
int main()
{
    int t;
    pre();
    scanf("%d",&t);
    while(t--)
    {
        long long n,res=1,temp,in,count;
        int k;
        bool flag=false,flag2=false;
        scanf("%lld%d",&n,&k);
        temp=n;
        while(k--)
        {
            scanf("%lld",&in);
            if(in==1)
            {
                flag=true;
                continue;
            }
            while(temp%in == 0)
                temp/=in;
        }
        
        if(flag)
        {
            printf("0\n");
            continue;
        }
        if(temp==n)
            flag2=true;
        int l=0;
        while(prime[l]*prime[l]<=temp && l<total)
        {
            count=0;
            while(temp % prime[l] == 0)
            {
                count++;
                temp/=prime[l];
            }
            res*=count+1;
            l++;
        }
        if(temp>1)
            res*=2;
        if(flag2)
            res--;
        printf("%lld\n",res);
    }
}

DCEPC11B-Boring Factorials

Boring Factorials

given below code for dcepc11b spoj or boring factorial spoj.

here the problem is based on two main concepts 

1 -> Wilson’s Theorem 

2 -> Inverse modulo (It can be found by Extended Euclidean Algorithm , Fermat’s Little Theorem ,Euler’s Theorem)

here in this problem i have used Fermat's theorem 

Wilson’s Theorem 

According to Wilson's Theorem     for all prime n;(for proof of Wilson's Theorem click on link)

Now from this we can write :

Here my solution get accepted in 1.83 sec can any body help me in optimizing this solution or any other solution which get accepted in lower time please mail me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL pow_mod(LL a,LL b,LL m)
{
 LL x=1,y=a;
 while(b>0)
 {
  if(b & 1)
   x=(x*y)%m;
  y=(y*y)%m;
  b>>=1;
 }
 return x;
}
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  LL n,p,i,result=-1,temp;
  scanf("%lld%lld",&n,&p);
  if(n>=p)
  {
   printf("0\n");
   continue;
  }
  for(i=n+1;i<p;i++)
  {
   temp=pow_mod(i,p-2,p);
   result=(result*temp)%p;
  }
  printf("%lld\n",p+result);
 }
 return 0;
}

aps-Amazing Prime Sequence

Amazing Prime Sequence

given below c code for aps spoj or amazing prime sequence.

If you have any quarry you can mail me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
int p[10000009];
long long res[10000009];
void pre()
{
 for(int i=2;i<=10000000;i++)
 {
  if(!p[i])
  {
   for(int j=i+i;j<=10000000;j+=i)
    if(!p[j])
     p[j]=i;
   res[i]=res[i-1]+i;
  }
  else
   res[i]=res[i-1]+p[i];
 }
}
int main()
{
 int t;
 pre();
 scanf("%d",&t);
 while(t--)
 {
  int n;
  scanf("%d",&n);
  printf("%lld\n",res[n]);
 }
 return 0;
}

WPC5I-LCM

LCM

given below c code for wpc5i spoj or lcm spoj.

If you have any problem you can ask me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,m;
  scanf("%d%d",&n,&m);
  map<int ,int>mp1,mp2,result;
  map<int ,int>::iterator t;
  for(int i=2;i*i<=n;i++)
  {
       while(n%i==0)
       {
           mp1[i]+=1;
           n/=i;
        }
  }
  if(n>1)
     mp1[n]+=1;
  for(int i=2;i*i<=m;i++)
  {
        while(m%i==0)
        {
            mp2[i]+=1;
            m/=i;
        }
  }
  if(m>1)
     mp2[m]+=1;
  long long k=1;
  for(t=mp1.begin();t!=mp1.end();t++)
  {
       if(t->second > mp2[t->first])
           result[t->first]=t->second;
  } 
  for(t=mp2.begin();t!=mp2.end();t++)
  {
       if(t->second > mp1[t->first] && result[t->first] < t->second)
            result[t->first]=t->second;
  }
  for(t=result.begin();t!=result.end();t++)
       for(int i=0;i<t->second;i++)
            k*=(long long)(t->first);
  printf("%lld\n",k);
 }
 return 0;
}

INS14B-TRISQRS

TRISQRS

Given below code is for ins14b spoj or trisqrs spoj.

Here the area of largest triangle possible in a square is (N*N)/2;

So we have to count the total number of divisors of  (N*N)/2.

My algorithm is very time consuming if any one can suggest me more fast algorithm for finding total number of divisors of a number please comment or mail me @ :-> raj.nishant360@gmail.com .That will be very help full to me.

#include <bits/stdc++.h>
using namespace std;
int num[1000009]={0};
void pre()
{
 for(int i=2;i<=1000;i++)
 {
  if(!num[i])
  for(int j=i*i;j<=1000000;j+=i)
   if(!num[j])
    num[j]=i;
 }
}
int main()
{
 int t;
 pre();
 scanf("%d",&t);
 while(t--)
 {
  int n;
  scanf("%d",&n);
  if(n&1){
   printf("0\n");
   continue;}
  n*=n;
  n>>=1;
  cout<<n<<endl;
  map<int ,int >mp;
  map<int ,int >::iterator t;
  if(num[n]!= 0)
   while(n%num[n] == 0)
   {
    mp[num[n]]+=1;
    if(num[n] == 0)
     break;
    n/=num[n];
    if(num[n]==0)
     break;
   }
  mp[n]+=1;
  int result =1;
  for(t=mp.begin();t!=mp.end();t++)
   result *= (t->second + 1);
  printf("%d\n",result);
 }
 return 0;
}