UVA 11889 Benefit

#include<bits/stdc++.h>
using namespace std;
#define SIZE 10000010
long long i,j,status[10000010]={0};
vector<long long >vec;
void seive ()
{
    memset(status,0,sizeof(status));
    status[0]=1;
    status[1]=1;
    for(i=4;i<SIZE;i+=2)
        status[i]=1;
    for(i=3;i*i<=SIZE;i+=2)
    {
        if(status[i]==0)
        {
            for(j=i*i;j<=SIZE;j+=2*i)
                status[j]=1;
        }
    }
    vec.clear();
    vec.push_back(2);
    for(i=3;i<=SIZE;i+=2)
    {
        if(status[i]==0)
            vec.push_back(i);
    }
}
int power (int a, int b)
{
    int ret = 1;
    for ( int i = 1; i <= b; i++ )
        ret *= a;
    return ret;
}

long long calculate(long long x,long long y)
{
    long long rslt=1,cnt=0,cnt1=0;
    for(i=0; i<550 && vec[i]<=x && vec[i]<=y; i++)
    {
        cnt=0,cnt1=0;
        while(x%vec[i]==0)
        {
            x=x/vec[i];
            cnt++;
        }
        while(y%vec[i]==0)
        {
            y=y/vec[i];
            cnt1++;
        }
        if(cnt1>cnt)
            rslt=rslt*power(vec[i],cnt1);
    }
    if(y>1 && x==1) rslt = rslt * y;
    return rslt;
}
main()
{
    seive();
    long long ts;
    cin>>ts;
    while(ts--)
    {
        long long a,b,ans=1;
        cin>>a>>b;
        if(b%a==0)
        {
            cout<<calculate(a,b)<<endl;
        }
        else
            printf("NO SOLUTION\n");
    }
}