c - 数学/大数挑战需要帮助

Question

我正在为以下代码（/挑战）而苦苦挣扎，我想知道解决它的最佳方法是什么。

伪（类似）代码

如果我正确理解代码，它会：

var val = 1
foreach (char in firstargument):
  val = val * ((ascii)char + 27137)

if (val == 92156295871308407838808214521283596197005567493826981266515267734732800)
  print "correct"
else
  print "incorrect"

其中 'firstargument' 是传递给程序的参数，例如：./program 123456...

实际代码

#define _GNU_SOURCE
#include <unistd.h> 
#include <string.h>
#include <stdio.h>
#include <gmp.h>

int main(int argc, char *argv[])
{
    mpz_t val, mul, cmpval;
    char str[513];
    int n = 0;

    mpz_init(val);
    mpz_set_ui(val, 1);
    mpz_init(mul);
    mpz_init(cmpval);
    mpz_set_str(cmpval, "92156295871308407838808214521283596197005567493826981266515267734732800", 10);

    if (argc < 2)
    {
        printf("%s <string>\n", argv[0]);
        return -1;
    }

    strncpy(str, argv[1], 512);

    for (n = 0; n < strlen(str); n++)
    {
        mpz_set_ui(mul, (unsigned long)(str[n] + 27137));
        mpz_mul(val, val, mul);
    }

    if (!(n = mpz_cmp(val, cmpval)))
    {
        printf("correct.\n");
    }
    else 
    {
        printf("incorrect.\n");
    }

    return 0;
}

Answer 1

我会从这样的角度来处理这个问题，即大数必须被整除((ascii)theVeryLastChar + 27137)- 并尝试找出最后一个字符是什么 - 然后除以它并为“倒数第二个字符”等工作。

Answer 2

这是一个小 Prolog 程序来计算解决方案，首先是具有较低 ASCII 代码的字母。

solve(A) :-
    number_anagram(92156295871308407838808214521283596197005567493826981266515267734732800, L),
    atom_codes(A,L).

number_anagram(N, L) :-
    number_anagram(N, 32, L).

number_anagram(1, 126, []).
number_anagram(N, C, [C|R]) :-
    N > 1,
    F is C + 27137,
    N mod F =:= 0,
    N1 is N / F,
    number_anagram(N1, C, R).
number_anagram(N, C, L) :-
    C < 126,
    C1 is C + 1,
    number_anagram(N, C1, L).

事实证明只有一种解决方案：

$ swipl 

[...]

?- ['number-anagram.pl'].
% number-anagram.pl compiled 0.00 sec, 1,636 bytes
true.

?- solve(A).
A = abbefhiooooorrsy ;
false.

Answer 3

I think this is also known as the chinese remainder theorem/problem. The diogenes algorithm is the solution.