UVa 11889 - Benefit Solution

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
bitset<3164> p;
vector<long long> prime;
void calc(){
    long long tmp=3163;
    long long tmp2=57;
    for(long long i=2;i<=tmp;i++){
        if(!p[i]){
            prime.push_back(i);
            if(i<=tmp2)
                for(long long j=i*i;j<=tmp;j+=i)
                    p[j]=1;
            }
        }
    }
int main(){
    calc();
    ios::sync_with_stdio(0);
    long long t;
    cin>>t;
    while(t--){
        long long a,c;
        cin>>a>>c;
        if(c%a!=0)
            cout<<"NO SOLUTION"<<endl;
        else{
            long long ans=1;
            for(long long i=0;i<prime.size();i++){
                long long x=0,y=0;
                while(a%prime[i]==0)
                    x++,a/=prime[i];
                while(c%prime[i]==0)
                    y++,c/=prime[i];
                if(x==y)
                    continue;
                while(y--)
                    ans*=prime[i];
            }
            if(a==1)
                ans*=c;
            cout<<ans<<endl;
        }
    }
}