UVA - 10484 - Divisibility Of Factors

Problem Link: https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1425

Idea: If some number a is divisible by d.Then we could say that, if a = p^i*q^j  and d=p^r*q^f then i and j must be greater or equal ofr and f respectively.So, we have to prime factorize the number given n.Then check if each prime number which are in n is greater or less with compare to prime factors of m.if power of prime factors of m is greater than n ,the answer is zero. Otherwise, multiplication of powers of each factor of n is the answer.

If n is 0 then answer depens on m.if m is 1 than answer is one.


Code First Then See Solution


Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 110
#define ll long long

int a[mx+10];
vector <int> v;

void seive()
{
    memset(a,0,sizeof(a));
    for(int i=2;i<sqrt(mx);i++)
    {
        if(a[i]==0)
        {
            for(int j=i*i;j<=mx;j+=i)
                a[j]=1;
        }
    }
    v.push_back(2);
    for(int i=3;i<=mx;i+=2)
    {
        if(a[i]==0)
            v.push_back(i);
    }
}

int main()
{
    ll n,m;
    seive();
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        if(m<0)
        m*=(-1);
        if(n==0)
          {
              if(m==1)
              {
                cout<<1<<endl;
                continue;
              }
              else
              {
                cout<<0<<endl;
                continue;
              }

          }
        int b[110];
        memset(b,0,sizeof(b));
        int k=0;
        for(int i=0;i<v.size()&&v[i]<=n;i++)
        {
            int f=n,cnt=0;
            while(f>=v[i])
            {
                cnt+=f/v[i];
                f/=v[i];
            }
            if(cnt>0)
            b[v[i]]=cnt;
        }
        ll res=1;
        for(int i=0;i<v.size()&&m>=v[i];i++)
        {
            if(m%v[i]==0)
            {
                int cn=0;
                while(m%v[i]==0)
                {
                    cn++;
                    m/=v[i];
                    b[v[i]]--;
                    if(b[v[i]]<0)
                    {
                        res=0;
                        break;
                    }
                }
                if(res==0)
                    break;
            }
        }

        if(m!=1)
            res=0;

        for(int i=0;i<101;i++)
        {
            if(b[i]!=0)
              res*=(b[i]+1);
        }
        cout<<res<<endl;
    }
    return 0;

}