UVA 12703 - Little Rakin

UVA Aug 31, 2020

Problem PDF

Solution:

/******************************************************************
***   Problem       :                                           ***
***   Author        : Shipu Ahamed (Psycho Timekiller)          ***
***   E-mail        : [email protected]                   ***
***   University    : BUBT,Dept. of CSE                         ***
***   Team          : BUBT_Psycho                               ***
***   My Blog       : http://shipuahamed.blogspot.com           ***
***   Facebook      : http://www.facebook.com/DeesheharaShipu   ***
******************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define pi 2*acos(0.0)
#define all(v) v.begin(),v.end()

//input
#define si(t) scanf("%d",&t)
#define sl(t) scanf("%lld",&t)
#define sf(t) scanf("%f",&t)
#define sd(t) scanf("%lf",&t)
#define sc(c) scanf("%c",&c)
#define sii(a,b) scanf("%d%d",&a,&b)
#define sll(a,b) scanf("%lld%lld",&a,&b)

//Output
#define P(a) printf("%d\n",a)
#define PL(a) printf("%lld\n",a)
#define PF(a) printf("%f\n",a)
#define PDB(a) printf("%lf\n",a)
#define PS(a) printf("%s\n",a)
#define PSN(a) printf("%s ",a)
#define PN(a) printf("%d ",a)
#define PLN(a) printf("%lld ",a)
#define PFN(a) printf("%f ",a)
#define PDBN(a) printf("%lf ",a)
#define PP(a,b) printf("%d %d\n",a,b)
#define PPN(a,b) printf("%d %d ",a,b)
#define PPL(a,b) printf("%lld %lld\n",a,b)
#define PPLN(a,b) printf("%lld %lld ",a,b)

#define CP(a) cout< pii;
typedef  pair piii;
typedef  pair pll;
typedef  pair psi;
typedef  vector vi;
typedef  vector vll;
typedef  vector vpii;
typedef  vector vs;
typedef  set si;
typedef  set ss;
typedef  map mii;
typedef  map mll;
typedef  map msi;

template string toString( T Number ){stringstream st;st << Number;return st.str();}
template  T SOD(T n) {__typeof(n) sum=0;for(__typeof(n) i=1;i*i<=n;i++)sum+=(n%i)?0:((i*i==n)?i:i+n/i);return sum;}


//For Define
#define forab(i,a,b) for(__typeof(b) i=(a);i<=(b);i++)
#define for0(i,n) forab(i,0,(n)-1)
#define for1(i,n) forab(i,1,n)
#define rforab(i,b,a) for(__typeof(b) i=(b);i>=(a);i--)
#define rfor0(i,n) rforba(i,(n)-1,0)
#define rfor1(i,n) rforba(i,n,1)
#define forstl(i,s) for(__typeof((s).end()) i=(s).begin(); i != (s).end(); i++)

//Debug
#define dbg(x) cout << #x << " -> " << (x) << endl;
#define dbgsarr(i,a) cout<<#a<<"["< "< "< "<>p ; return p;}

ll pow(ll a,ll b, ll m) { ll res = 1; while(b) { if(b & 1) { res = ( (res % m) * (a % m) ) %m ; } a= ((a%m) * (a%m)) %m; b >>= 1; } return res; }
ll modInverse(ll a, ll m){return pow(a,m-2,m);}

////============ CONSTANT ===============////
#define mx7   10000007
#define mx6   1000006
#define mx5   100005
#define inf   1<<30                                           //infinity value
#define eps   1e-9
#define mx    (10010)
#define mod   1000000007
////=====================================////

bool prime[mx];
int pd[mx];


struct factorize
{
    int prime,pow=0;
};


void seive()
{
    prime[0]=1;
    prime[0]=1;
    for(int i=2;i<=mx;i+=2)
        pd[i]=2,prime[i]=1;

    prime[2]=0;

    for(ll i=3;i<=mx;i+=2)
    {
        if(!prime[i])
        {
            pd[i]=i;
            ll mul=i<<1;
            ll j=i;
            for(j*=i;j<=mx;j+=mul)
            {
                pd[j]=i;
                prime[j]=1;
            }
        }
    }
}

vectorv[50];
void fact(int n,int pos)
{

    while(n!=1)
    {
        int s=pd[n],cnt=0;
        while(n%s==0)
        {
           n/=s,cnt++;
        }
        factorize res;
        res.pow=cnt;
        res.prime=s;
        v[pos].pb(res);
    }

}


int main()
{
    seive();
    int t;
    si(t);
    while(t--)
    {
        int n,a,b;
        sii(n,a),si(b);

        fact(a,0);
        fact(b,1);

        forab(i,2,n)
        {
            vectoradd;
            mii mp;
            for0(j,sz(v[i-1]))
            {
                mp[v[i-1][j].prime]+= v[i-1][j].pow;
            }
            for0(j,sz(v[i-2]))
            {
                mp[v[i-2][j].prime]+= v[i-2][j].pow;
            }
            forstl(it,mp)
            {
                factorize res;
                res.prime= it->ff;
                res.pow= it->se;
                add.pb(res);
            }
            v[i]=add;
        }

        int s=sz(v[n]);
        for0(i,s)
        {
            PP(v[n][i].prime,v[n][i].pow);
        }
        nl;
        for0(i,n+1)
        {
            v[i].clear();
        }

    }
    return 0;
}


https://github.com/Shipu/OnlineJudgeProblemSolutionWithCPlusPlus/tree/master/uva/12703/12703.cpp

Tags

Shipu Ahamed

CSPO® | Partly Product, Project Manager and Partly Software Engineer.

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.