Poj Solution 1783

http://poj.org/problem?id=1783

#include<iostream>
using namespace std;
int prime[200],t[200],n;

void doprime()
{int i,j;
    n=1;
    prime[0]=2;
    for(i=3;i<1000;i++)
    {for(j=0;j<n;j++)if(i%prime[j]==0)break;

    if(j==n)prime[n++]=i;
    }
}

void fjie(int a[200],int s)
{int i;
for(i=0;i<200;i++)a[i]=0;

for(i=0;i<n&&s>1;i++)
while(s%prime[i]==0){a[i]++;s/=prime[i];}
}

int fn[101][200],fd[101][200],k,m,fdp[101][200],fnp[101][200]; 
int now[200];

void init()
{int i,s,j,h;
cin>>s;
fjie(now,s);
cin>>k;

for(i=0;i<k;i++)
{cin>>s;fjie(fn[i],s);
 h=0;
 for(j=0;j<n;j++)if(fn[i][j])fnp[i][h++]=j;

 fnp[i][h]=-1;


cin>>s;fjie(fd[i],s);
h=0;
 for(j=0;j<n;j++)if(fd[i][j])fdp[i][h++]=j;

 fdp[i][h]=-1;
}

}
//long ci=0;
void doit()
{int key=0;int i,j,temp;
for(j=0;j<n;j++){if(j&&now[j])key++;}
if(!key){m--;cout<<now[0];if(m)cout<<" ";}

while(m--)
{for(i=0;i<k;i++)
{for(j=0;fdp[i][j]>=0;j++){if(now[fdp[i][j]]<fd[i][fdp[i][j]])break;}
    
     if(fdp[i][j]<0)break;
    }
for(j=0;fdp[i][j]>=0;j++){temp=now[fdp[i][j]];now[fdp[i][j]]=now[fdp[i][j]]-fd[i][fdp[i][j]];
                        if(fdp[i][j]&&temp&&!now[fdp[i][j]])key--;}
for(j=0;fnp[i][j]>=0;j++){temp=now[fnp[i][j]];now[fnp[i][j]]=now[fnp[i][j]]+fn[i][fnp[i][j]];
                        if(fnp[i][j]&&!temp&&now[fnp[i][j]])key++;}


//ci++;
if(!key){cout<<now[0];if(m)cout<<" ";}
else m++;
}

cout<<endl;
//cout<<ci<<endl;
}

int main()
{doprime();
    while(1)
{cin>>m;
if(!m)break;
init();
doit();
}
return 0;
}