斑的家

#include<iostream>
#include<string.h>
#include<stdio.h>
#define SIZE 5001
using namespace std;
short p[SIZE];
void init();
/*
 * AUTHOR : benbendog
 * DATE   : 2011/2/1
 * PROBLEM: test if two numbers a,b satisfy a%b
 *          if yes,
                    print a/b if a/b < 10^101
                    print -1  otherwise
            print 0 otherwise
 * Solution:
              sieve table , prime <=5000
              factor set, n[2] = 5 , meaning
              the number has 2^5 etc
              factor sets are used to
              test divisibility
              make a biginteger to print
              the output
 */
struct number
{
    number(){memset(n,false,sizeof(n));}
    void add(int a,int b);
    void output();
    bool divisible(const struct number & a);
    void divideAndPrint(const struct number & a);
    short n[SIZE];
};
bool mul(int * m,int s);
int main()
{
    init();
    int a,b,c,d,i;

    while(cin>>a>>b)
    {
        struct number num[2];
        for(i = 0 ; i < a ; i++ )
        {
            cin>>c>>d;
            num[0].add(c,d);
        }
      //  num[0].output();
        for(i = 0 ;i < b ; i++)
        {
            cin>>c>>d;
            num[1].add(c,d);
        }
        //num[1].output();
        if(num[0].divisible(num[1]))
        {
            num[0].divideAndPrint(num[1]);
        }
        else
            cout<<0<<endl;
    }
    return 0;
}
void number::add(int a,int b)
{
    if(a-b < b)b = a-b;
    for(int i = 0,k = a ; i < b ;k--,i++)
    {
        int  t = k;
        while(t!=1)
        {
             n[p[t]]++;
            t = t/p[t];
        }
    }
    for(int i = 1 ; i <= b ;i++)
    {
        int t = i;
        while(t!=1)
        {
              n[p[t]]--;
            t = t/p[t];
        }
    }
}
void init()
{
    memset(p,false,sizeof(p));
    p[1] = 1;
    for(int i = 2 ; i < SIZE;i++)
    {
        if(p[i])continue;
        for(int j = i ; j < SIZE;j+=i)
            p[j] = i ;
    }
}
 void number::output()
 {
     for(int i = 2 ; i < SIZE;i++)
     {
         if(n[i])
         {
             printf("n[%d] has %d \n",i,n[i]);
         }
     }
 }
bool number::divisible(const struct number & a)
{
    for(int i = 2 ;i < SIZE;i++)
        if(n[i]< a.n[i])return false;
    return true;
}
void number::divideAndPrint(const struct number & b)
{
    bool f = false;
    for(int i = 2 ;i < SIZE;i++)
        n[i]-=b.n[i];
    int a[101];
    memset(a,false,sizeof(a));
    a[0] =1;

    for(int i =2 ; i < SIZE;i++)
    {
        for(int j = 0 ; j < n[i] ; j++)
            if(mul(a,i)){f = true;goto L;}
    }
L:
    if(f)cout<<-1<<endl;
    else
    {
         int j = 100 ;
         while(j > 0 && a[j]==0)j--;
         while(j > -1)
             cout<<a[j--];
         cout<<endl;
    }

}
bool mul(int * m,int s)
{
    for(int i = 0 ;  i < 101 ; i++)
    {
        m[i]*=s;
    }
    for(int i = 0 ; i< 100 ; i++)
    {
        m[i+1]+=m[i]/10;
        m[i]%=10;
    }
    if(m[100])return true;
    return false;
}