WF Factors

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <assert.h>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef long long ll;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mp make_pair
#define go(i,n) for(int i=0;i<n;i++)
#define go3(i,j,n) for(int i=j;i<n;i++)
#define inf 1000000000
#define fi first
#define se second
#define un unsigned long long
#define oo 9223372036854775808ull // 2^63


int a[1000001];
int primes[10000];
int yk=0;

void sieve(){
  go(i,100000) a[i]=1;

  a[0]=a[1] = 0;

  for(int i=2;i*i<=100000;i++)
   if(a[i])
    for(ll j= i*1ll*i;j<=100000;j+=i)
      {
       a[j]=0;
      }
  go(i,100000) if(a[i]) primes[yk++] = i;
}


int cnt=0;
int nx=0;

map<un,un> memo;
set<un> dan;

int col[20];

// calculates the value S! / (s1! * s2! * S3! *s4! ...sk!)
// checks whether it is number  < 2^63
// if yes, registers it
// si are in array col, y is their number
void check(int y,un san){

  int mf = 0;
  int sp = 2;
  un s=1ll;

  go(i,y) mf+=col[i];


  int uk = 0;
  int ad = col[0];

  while(uk<y) {

   while(ad<=1 && uk<y)
     ad=col[++uk];


   if(uk==y) break;

   assert(ad!=0);

   while( (s%ad)==0 && ad>1){
     s=s/ad;
     ad--;
   }

   if(ad>1) s*=1ull*(mf--);

  }


  bool flag = false;

  for(;mf>=2;mf--)
   {
    if(oo/mf > s)
     s*=1ull*mf;
    else flag = true;
   }

   if(flag) return;

   if(present(dan,s)){
     if(!memo.count(s))
      memo[s]=san;
     memo[s] = min(memo[s],san);
   }
}


void rec(int y,un san){
   cnt++;
   nx=max(nx,y);

   check(y+1,san);

   if( oo/primes[y] >= san)
    {
     col[y]++;
     rec(y,san*1ull*primes[y]);
     col[y]--;
    }

    if(y>1 && col[y-1]<col[y]) return; //guarantees that prev value is not less than current

   if( oo/primes[y+1] >= san)
     {
      col[y+1]++;
      rec(y+1,san*1ull*primes[y+1]);
      col[y+1]--;
     }
}


void read(){
 sieve();
 un n;
 vector<un> v;
 string s;

 while(cin>>n){
  dan.insert(n);
  v.pb(n);
 }

 memset(col,0,sizeof col);

 rec(0,1ull);

 memo[1] = 2; //treat one by hand


 go(i,sz(v))
   cout<<v[i]<<" "<<memo[v[i]]<<endl;



}

int main(){

read();

return 0;}