找到一个数字的排列的gcd [英] Finding gcd of permutations of a Number
问题描述
以下是问题的链接：
http://www.spoj.com/problems/GCD/
考虑自然数的十进制表示法N.
找到可以通过置换给定数字中的数字获得的所有数字的最大公约数（GCD）。允许前导零。
Consider the decimal representation of a natural number N. Find the greatest common divisor (GCD) of all numbers that can be obtained by permuting the digits in the given number. Leading zeroes are allowed.
我使用以下方法：
http://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.最后，如果所有数字都是0，则GCD将是27， 3,6或9和27划分一个置换，并且如果所有数字都是0或9，则划分81，并且81划分一个置换。
First, if all the digits are the same, there is only one number and that is the GCD. As was pointed out before, if 3 or 9 is a factor of one permutation it will be a factor of them all. Otherwise, imagine swapping just the ones and tens digit when they are different. The GCD of these two has to divide 100a+10b+c−100a+10c+b=9(b−c) where b and c are single digits. For the GCD of all the numbers to have a factor 2, all the digits must be even. For the GCD to have a factor 4, all the digits must be 0, 4, or 8 and for 8 they must be 0 or 8. Similarly for 5 and 7. Finally, the GCD will be 27 if all the digits are 0,3,6, or 9 and 27 divides one permutation and 81 if all the digits are 0 or 9 and 81 divides one permutation. Can you prove the last assertion?
我的解决方案：
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。
我似乎找不到任何可能错误的边缘情况。
But it is giving WA. I cannot seem to find any edge case on where it might be wrong.
请告诉我在哪里错了。感谢：）
Please tell me where am i wrong. Thanks :)
推荐答案
首先，如果所有数字都相同，
First, if all the digits are the same, there is only one number and that is the GCD.
你不处理这个（第一个）case
You don't handle this (first) case
所以用你的代码 11 ， 111 ， 44 给出错误的答案。
So with your code all of 11, 111, 44 gives wrong answer.
[..] 81如果所有的数字都是0或9， / p>
[..] 81 if all the digits are 0 or 9 and 81 divides one permutation.
似乎你的测试错误：
if ((rem(str, 81) == 0) && (gcdf(gcds, 3) == 3))
您是不是要查询：
if ((rem(str, 81) == 0) && (gcdf(gcds, 9) == 9))
您有3699个不一致的结果排列：
You have for permutation of 3699 inconsistent results:
27 for 3699, 3996, 6939, 6993, 9369, 9693, 9936
81 for 3969, 6399, 9396, 9639, 9963.
我的实现检查（对于int数）是：
My implementation to check (for int number) is:
int my_gcd(std::string str)
{
std::sort(str.begin(), str.end());
std::string first = str;
int gcd = atoi(first.c_str());
while (std::next_permutation(str.begin(), str.end())) {
gcd = gcdf(atoi(str.c_str()), gcd);
}
return gcd;
}
这篇关于找到一个数字的排列的gcd的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
