/******************************************************************
*** Problem : ***
*** Author : Shipu Ahamed (Psycho Timekiller) ***
*** E-mail : shipuahamed01@gmail.com ***
*** 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