c - 计算由k个有限素数构成的不重复数

我不明白下列问题的解决办法：
爱丽丝和鲍勃在玩游戏。
在这个游戏中，玩家应该同时用手显示一个0到1000万之间的整数。如果两个球员的数字相等，我们就平手了。否则，选手们轮流在一张纸上写下数字。
让A是Alice在匹配开始时显示的整数，让B是Bob显示的整数，写下的每个数字都必须是| A-B |因子的乘积，所有因子都是质数，不一定是不同的，属于整数A和B定义的区间。
爱丽丝总是先玩。
例如，如果A=2和B=5，则只有10个数字（Bob Wins）可以写在纸上，它们是：

8 = 2 x 2 x 2
12 = 2 × 2 × 3
20 = 2 × 2 × 5
18 = 2 × 3 × 3
30 = 2 × 3 × 5
50 = 2 × 5 × 5
27 = 3 × 3 × 3
45 = 3 × 3 × 5
75 = 3 × 5 × 5
125 = 5 × 5 × 5

输入有两个数字A和B，如前所述。
输出有一行单独包含比赛获胜者的名字，假设两个玩家都玩得最好。如果匹配，输出线应单独包含符号“？”.
以下是解决此问题的方法：

#include <stdio.h>
#include <math.h>
#include <string.h>

#define MAX 11234567

int primes[MAX], primeIndex;

inline void sieve(int limit) {

    bool sieve[limit];
    memset(sieve, 0 , sizeof(sieve));

    primeIndex = 0;
    primes[primeIndex] = 2;

    for (int i = 3; i < limit ; i += 2) {
        if(!sieve[i]){
            primes[++primeIndex] = i;
            for (int j = i + i; j <= limit; j += i) {
                sieve[j] = 1;
            }
        }
    }

    ++primeIndex;
}

inline int mul(int n) {
    int ret = 0;
    while (n > 0) {
        n /= 2;
        ret += n;
    }
    return ret;
}

inline void swap(int *a, int *b){
    int aux = *a;
    *a = *b;
    *b = aux;
}

int main(void) {
    int A, B;
    scanf("%d %d", &A, &B);

    if (A == B) {
        puts("?");
        return 0;
    }

    if (A > B) {
        swap(&A, &B);
    }


    sieve(B);

    int position_of_largest_prime;
    for (position_of_largest_prime = 0; position_of_largest_prime < primeIndex && primes[position_of_largest_prime] < A; ++position_of_largest_prime);

    int intervalBA = B - A;
    int primeCount = (primeIndex - position_of_largest_prime);

    puts(primeCount > 0 && mul(intervalBA + primeCount - 1) == mul(primeCount - 1) + mul(intervalBA) ? "Alice" : "Bob");

    return 0;
}

mul（intervalBA+primeCount-1）==mul（primeCount-1）+mul（intervalBA）
我不明白上述情况。
这是数论问题吗？
有人能帮我辨认出来吗？
正如回答中指出的那样，缺乏关于描述的信息。Here是指向该问题的链接，并提供了详细说明。

最佳答案

关于这个游戏的一些细节还没有完全解释清楚。例如，可能是爱丽丝和鲍勃在比赛开始时没有选择同一个号码，但是他们选择的号码之间没有素数。如果A=14，B=16，这是平局吗？如果是这样，我认为您提供的解决方案在所有情况下都不正确，因为在Bob的情况下，输出似乎是?而不是primeCount = 0。另外，我假设写下最后一个数字的人是赢家，但这在游戏描述中没有明确说明。
不过，你的首要问题似乎是关于所涉及的组合数学。如果我正确地理解了这个游戏，那么如果A和B之间有素数，我们需要确定这些素数的| B-A |的不同乘积的个数是偶数还是奇数。人们可能会问的第一个问题是，“有多少不同的产品？”计算这些的一个好方法是使用星条旗法。你可以阅读更多关于星和条的内容，但是在你的示例游戏中，需要选择一些素数，我称之为三星和两条，素数2和3之间的分隔线和3和5之间的分隔线。因此|B-A| = 3表示产品*|*|*，2 x 3 x 5表示产品**|*|，2 x 2 x 3表示产品*||**。请注意，条数比A和B之间（包括A和B）的间隔中的素数少一个。然后，作为一个组合问题，我们选择星体和棒子在整个序列中的位置。整个序列的长度是2 x 5 x 5，要选择的星位置的数目是intervalBA + primeCount - 1。
如果我们要计算存在的不同组合的数量，那么，我们将计算可以从intervalBA对象生成多少个大小intervalBA的组合。换句话说，我们将计算intervalBA + primeCount - 1选择intervalBA + primeCount - 1。然而，这个数字很容易超过你正在使用的计算机上的整数的大小，所以直接计算是不可行的。相反，我们应该找到一种方法来决定计算结果是偶数还是奇数，而不直接计算结果。
用卢卡斯定理可以判断结果是偶数还是奇数。我将提供一个关于定理的ahere和aWikipedia article的链接，其中一条评论讨论如何应用Lucas定理来回答使用数字的二进制表示组合是偶数还是奇数的问题。
解的intervalBA函数也可用于确定结果是偶数还是奇数，而无需直接计算结果。它所做的与用卢卡斯定理得到的解稍有不同。这不是我以前见过的，但我最终确定mul计算2的最大幂，它将除以mul(n)阶乘。用n来表示阶乘，choose!的基本定义通常是n。因此，条件k检查2除以分子的最大幂是否等于2除以分母的最大幂，其中n!/(k!(n-k)!)是mul(intervalBA + primeCount - 1) == mul(primeCount - 1) + mul(intervalBA)且n是intervalBA + primeCount - 1。如果除以分子的2的最大幂等于除以分母的2的最大幂，则k选择intervalBA将是奇数，爱丽丝将获胜。否则n选择k将是偶数，鲍勃将获胜。
如果正确地记录了解决方案中的代码，那么类似于解决方案中的代码的代码将更容易理解。