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;
} 

COMDIV - Number of common divisors

Number of common divisors

Given below code is for comdiv spoj or number of common divisor spoj.

Hint :- > sieve and the number of common divisor of two number will be the number of divisor of its GCD.

#include <bits/stdc++.h>
using namespace std;
int prime[100000];
bool check[1000009];
void pre()
{
    for(int i = 3 ; i<=1000 ; i+=2)
    {
        if(!check[i])
        {
            for(int j = i*i ; j<=1000000 ; j+=i)
                check[j] = true;
        }
    }
    int j  = 1;
    prime[0] = 2;
    for(int i = 3; i <=1000000 ; i+=2)
        if(!check[i])
            prime[j++] = i;
}
int main()
{
    pre();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        long long  gcd = __gcd(a,b);
        long long  res = 1;
        if(gcd == 1)
        {
            printf("1\n");
            continue;
        }
        for(int i = 0 ;i <= 78500 && prime[i] < gcd  && gcd; i++)
        {
            int count = 0;
            while(gcd%prime[i] == 0)
            {
                count++;
                gcd/=prime[i];
            }
            res *= (count + 1);
        }
        if(gcd > 1)
            res *= 2;
        printf("%lld\n",res);
    }
    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);
    }
}

IITKWPCF-Help Feluda with mathematical equations

Help Feluda with mathematical equations

Given below c++ code for iitkwpcf spoj or Help Feluda with mathematical equations spoj .
Here is the explanation of logic.
Given X²  + Y² + n = (X + Y)²
Now expanding it   
X²  + Y² + n = X²  + Y² + 2XY    ≡   n = 2XY   ≡  X = (n/2)*(1/y)
So we have to find only non-prime integral factor of “n/2” .and if “n” is odd then no integral “X” is possible so we will write 0 for all odd “n”.
Here my solution got accepted in 2.45 sec .Please help me to reduce the time complexity @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
#define LL long long
bool check(LL n)
{
    if(n==1)
        return true;
    for(LL i=2;i*i<=(n);i++)
        if(n%i==0)
            return true;
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n,temp;
        scanf("%lld",&n);
        if(n==0)
        {
            printf("0 0\n");
            continue;
        }
        if(n&1)
        {
            printf("0\n");
            continue;
        }
        n>>=1;
        map<LL,int>mp;
        map<LL,int>::iterator t;
        for(LL i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                if(check(i)){
                    mp[i]=1;
                }
                if(check(n/i))
                    mp[n/i]=1;
            }
        }
        printf("%d ",mp.size());
        for(t=mp.begin();t!=mp.end();t++)
            printf("%lld ",t->first);
        printf("\n");
    }
    return 0;
}

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;
}