学步园

题意：给出ai bi(i=1->n),M = a1^b1 * … * ai^bi * … * an^bn,求一个最小的整数x，使x! % M == 0.

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <algorithm>
#define M 1
#define N
#define inf 100000000
using namespace std;
long long pri[100];
int prime[100],top=0;
bool f;
void prime1(long long a,long long b)
{
    for(int i=0; i<top&&a!=1; i++)
    {
        if(a%prime[i]==0)
        {
            f=0;
            pri[prime[i]]+=b;
            a/=prime[i];
            --i;
        }
    }
}


int isprime(int a)
{
    int m=sqrt(a);
    for(int i=2;i<=m;i++)
    {
        if(a%i==0)
        return 0;
    }
    return 1;
}
int main()
{
//    freopen("ex.in","r",stdin);
    int t,n;
    long long a,b;
    scanf("%d",&t);


    for(int i=2;i<98;i++)
    if(isprime(i))
    prime[top++]=i;


    while(t--)
    {
        f=1;
        memset(pri,0,sizeof(pri));


        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%I64d%I64d",&a,&b);
            prime1(a,b);
        }
        if(f)
        {
            cout<<"0\n";
            continue;
        }


        long long l=1,r=0xfffffffffffffffLL,mid,c,temp;
        int flag;
        while(l<r)//二分真的很快！！！！！
        {
            mid=(l+r)>>1;
            flag=1;
            for(int i=0;i<top;i++)
            if(pri[prime[i]])
            {
                c=0;
                temp=mid;
                while(temp>=prime[i])
                {
                    c+=(temp/prime[i]);
                    temp/=prime[i];
                }
                if(c<pri[prime[i]])
                {
                    l=mid+1;
                    flag=0;
                    break;
                }
            }


            if(flag)
            r=mid;
        }
        cout<<l<<endl;
    }
    return 0;
}




//while(scanf("%d",&n))
//    {
//        memset(pri,0,sizeof(pri));
//        prime(n,1);
//        for(int i=1;i<=n;i++)
//        cout<<pri[i]<<" ";
//        cout<<endl;
//    }