ALL Number product resulted number divisor count

Problem: https://acm.timus.ru/problem.aspx?space=1&num=1049




#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base:: sync_with_stdio( false ); cin.tie(0); cout.tie(0);
int status[100000000/32];
bool Check(int N,int pos){return (bool)(N & (1<<pos));}
int Set(int N,int pos){ return N=N | (1<<pos);}
long long int arr[10000000];
long long int l=0,a,b=100000,n;


void sieve()
{
     long long int i,j,sqrtN;
     sqrtN = int( sqrt( b ) );
     for( i=3; i<=sqrtN; i+=2 )
     {
       if( Check(status[i/32],i%32)==0)
       {
         for(j=i*i; j<=b; j+=2*i)
         {
            status[j/32]=Set(status[j/32],j%32);
         }
       }
    }
    arr[0]=2;
    l=1;
    for(i=3;i<=b;i+=2)
    {
        if(Check(status[i/32],i%32)==0)
        {
            arr[l]=i;
            l++;
        }
     }
}


long long int p[10000];
long long int e[10000];
int nk=0;

void decomp(long long int a)
{
    long long int sqrtA=sqrt(a);
    for(long long int i=0; i<l && arr[i]<=sqrtA; i++)
    {
        int count=0;
        /*if(Check(status[a/32],a%32)==0)
        {
            break;
        }*/
        if(a%arr[i]==0)
        {
            while(a%arr[i]==0)
            {
                count++;
                a=a/arr[i];
            }

            if(count>0)
            {
                p[nk]=arr[i];
                e[nk]=count;
                nk++;
            }
        }
        sqrtA=sqrt(a);
    }
    if(a!=1)    ///for last prime
    {
        p[nk]=a;
        e[nk]=1;
        nk++;
    }
}


int main()
{
    fast
    sieve();  ///sieve must be out of any loop
    set<ll>s;
    //cout<<arr[l-1]<<endl;
    map<ll,ll>m;
    long long int a=1,b=1,k=0,c,d=1,l=0;
    for(int i=0; i<10; i++)
    {
        cin>>c;
        decomp(c);
        for(int j=0; j<nk; j++)
        {
            m[p[j]]+=e[j];
            //cout<<p[j]<<" "<<m[p[j]]<<endl;
            s.insert(p[j]);
        }
        nk=0;

    }
    for(auto it=s.begin(); it!=s.end(); it++)
    {
        m[*it]++;
        b*=m[*it];
    }
    cout<<b%10<<endl;
    return 0;
}

Comments

Popular posts from this blog

C++ STL practice problem link

Binary Index Tree(BIT)

Combinatorics