Нахождение gcd перестановок числа

Вот ссылка на проблему:

http://www.spoj.com/problems/GCD/

Рассмотрим десятичное представление натурального числа N.
Найти наибольший общий делитель (GCD) из всех чисел, которые можно получить, переставляя цифры в данном числе. Ведущие нули допускаются.

Я работал над следующим подходом:
https://math.stackexchange.com/a/22453

Во-первых, если все цифры одинаковы, есть только одно число, и это GCD. Как указывалось ранее, если 3 или 9 является фактором одной перестановки, он будет фактором их всех. В противном случае, представьте, что нужно поменять местами только цифры и десятки, когда они разные. GCD этих двух должен делить 100a + 10b + c-100a + 10c + b = 9 (b-c), где b и c — однозначные цифры. Чтобы GCD всех чисел имел коэффициент 2, все цифры должны быть четными. Чтобы GCD имел коэффициент 4, все цифры должны быть 0, 4 или 8, а для 8 они должны быть 0 или 8. Аналогично для 5 и 7. Наконец, GCD будет 27, если все цифры 0, 3,6, или 9 и 27 делит одну перестановку и 81, если все цифры 0 или 9, а 81 делит одну перестановку. Можете ли вы доказать последнее утверждение?

Мое решение:
http://ideone.com/VMUb6w

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>using namespace std;

int rem(string str, int a){
if (str.empty())
{
return 0;
}
int temp = (str[str.length() - 1] - '0') % a;
int temp2 = 10 % a;
str.erase(str.length() - 1);
int temp3 = (rem(str, a)*temp2) % a;
return (temp3 + temp) % a;
}int gcdf(int a, int b)
{
return b ? gcdf(b, a%b) : a;
}int main(){
string str;
while (cin >> str)
{

size_t l = str.length();
vector<int> digit;
int sum = 0;
int frequency[9];
for (int i = 0; i<9; i++)
frequency[i] = 0;
int zero_sum = 0;
for (size_t i = 0; i < l; i++)
{
if (str.at(i) != '0')
{
frequency[str.at(i) - '1']++;
sum += str.at(i) - '0';
}
else
{
zero_sum++;
}
}

for (size_t i = 0; i < 9; i++)
{
if (frequency[i])
{
digit.push_back(i + 1);
}
}
int gcds = 0, gcd = 1;
for (size_t i = 0; i < digit.size(); i++)
{
gcds = gcdf(digit[i], gcds);
}
if (gcdf(3, gcds) == 1)
{
gcd *= gcds;
}
if (gcds == 6)
{
gcd *= 2;
}
if ((rem(str, 81) == 0) && (gcdf(gcds, 3) == 3))
{
gcd *= 81;
}
else
{
if ((rem(str, 27) == 0) && (gcdf(gcds, 3) == 3))
{
gcd *= 27;
}
else
{
if (sum % 9 == 0)
{
gcd *= 9;
}
else
{
if (sum % 3 == 0)
{
gcd *= 3;
}
}
}
}
if((digit.size()==1)&&(zero_sum==0))
cout<<str;
else
cout << gcd << endl;}
return 0;
}

Но это дает WA.
Я не могу найти какой-либо крайний случай, где это может быть неправильно.

Пожалуйста, скажите мне, где я не прав. Спасибо 🙂