Sisoku Solver in C++

sisoku.cpp

#include <cstdio>
#include <vector>

using namespace std;

int gcd(int a, int b)
{
     if(a < b) gcd(b, a);
     if(b == 0) return a;
     return gcd(b,a%b);
}

class mint
{
public:
     int m,n;
     mint():m(0),n(1){}
     mint(int i):m(i),n(1){}
     mint(int i,int j){
	  if(j < 0) i = -i, j = -j;
	  int x=gcd(((i<0)?-i:i),j);
	  m=i/x;
	  n=j/x;
     }
     mint operator+(const mint & o){return mint(m*o.n+o.m*n,n*o.n);}
     mint operator-(const mint & o){return mint(m*o.n-o.m*n,n*o.n);}
     mint operator*(const mint & o){return mint(m*o.m,n*o.n);}
     mint operator/(const mint & o){return mint(m*o.n,n*o.m);}
     bool operator==(const mint & o){return o.m==m&&o.n==n;}
     mint clone(){return mint(m,n);}
};

int N;
mint A;
mint a[10];

vector<mint> bt;

void solve()
{
     if(N == 1){
	  if(a[0] == A){
	       printf("solved\n");
	       for(vector<mint>::iterator it = bt.begin();it != bt.end();it++){
		    if(it->n != 1){
			 printf("%d/%d ", it->m, it->n);
		    }else{
			 printf("%d ", it->m);
		    }
	       }
	       puts("");
	  }
	  return;
     }

     mint x,y;

     for(int i=N-1;i>=0;i--){
	  swap(a[N-1], a[i]);

	  for(int j=N-2;j>=0;j--){
	       swap(a[N-2], a[j]);

	       x = a[N-1].clone();
	       y = a[N-2].clone();
	       bt.push_back(x);
	       bt.push_back(y);
	       N--;

	       a[N-1] = x+y;
	       solve();

	       a[N-1] = y-x;
	       solve();
	       
	       a[N-1] = x-y;
	       solve();

	       a[N-1] = x*y;
	       solve();

	       if(x.m > 0){
		    a[N-1] = y/x;
		    solve();
	       }
	       if(y.m > 0){
		    a[N-1] = x/y;
		    solve();
	       }

	       N++;
	       bt.pop_back();
	       bt.pop_back();
	       a[N-1] = x;
	       a[N-2] = y;
	  }

	  for(int j=N-2;j>=1;j--){
	       swap(a[j],a[j-1]);
	  }
     }

     for(int i=N-1;i>=1;i--){
	  swap(a[i],a[i-1]);
     }
}

main()
{
     int n,m;
     scanf("%d%d",&n,&m);
     A = mint(n,m);

     scanf("%d",&N);

     int t;
     for(int i=0;i<N;i++){
	  scanf("%d",&t);
	  a[i] = t;
     }
     
     solve();
}