Hello. As some of you may know, the Mount Allison Programming Showdown 2020 took place yesterday, and I had a question about the Divide and Conquer problem.

You can read the problem yourself, but basically, the problem gives you two integers $$$b$$$ and $$$d$$$, where $$$1 < b, d < 2^{63}$$$ and $$$d$$$ is prime, and then asks you if there exists an $$$m$$$ such that $$$b^m \equiv -1 \pmod{d}$$$. You need to output yes if such an $$$m$$$ exists and output no otherwise. (This is an oversimplification of the problem because the actual problem statement is quite long, so it is possible I misread what it is asking, but I am just giving this short summary of the problem so that I don't have to repeat the whole problem statement in this post.)

Here is how my solution works:

• If $$$d=2$$$, then $$$m$$$ exists if and only if $$$b$$$ is odd.
• If $$$d$$$ is an odd prime, then $$$m$$$ exists if and only if $$$b$$$ has even order in the group of units $$$\pmod{d}$$$.
• • PROOF: If $$$m$$$ exists, then we can let $$$m'$$$ is the smallest positive integer such that $$$b^{m'}\equiv -1\pmod{d}$$$. Thus, the order of $$$b$$$ must be greater than $$$m'$$$. Moreover, we have $$$b^{2m'}\equiv (-1)^2\equiv 1\pmod{d}$$$, so the order of $$$b$$$ must be at most $$$2m'$$$. Now, for any integer $$$m < n < 2m'$$$, it holds that $$$0 < n-m' < m'$$$, so $$$b^{n-m'}\not\equiv -1\pmod{d}$$$ since $$$m'$$$ is the smallest positive integer such that $$$b^{m'}\equiv -1\pmod{d}$$$ and $$$n-m' < m'$$$. Thus, $$$b^n\equiv b^mb^{n-m}\equiv -b^{n-m}\not\equiv 1\pmod{d}$$$, so the order of $$$b$$$ is not $$$n$$$ for any $$$m' < n < 2m'$$$. Therefore, the order of $$$b$$$ must be $$$2m'$$$, so the order of $$$b$$$ is even.
• • PROOF CONTINUED: If $$$b$$$ has even order, then let $$$2m$$$ be the order of $$$b$$$. Then, $$$b^{2m}\equiv (b^m)^2\equiv 1\pmod{d}$$$. Thus, either $$$b^m\equiv -1\pmod{d}$$$ or $$$b^m\equiv 1\pmod{d}$$$. However, since $$$2m$$$ is the order of $$$b$$$, $$$b^m\not\equiv 1\pmod{d}$$$, so it must be that $$$b^m\equiv -1\pmod{d}$$$.
• • Now, to see if the order of $$$b$$$ is even, calculate $$$b^n\pmod{d}$$$, where $$$n$$$ is the biggest odd factor of $$$d-1$$$. If $$$b^n\equiv 1\pmod{d}$$$, then the order of $$$b$$$ divides $$$n$$$, so $$$b$$$ has odd order, so output no.
• • Otherwise, if $$$b^n\not\equiv 1\pmod{d}$$$, then the order of $$$b$$$ does not divide $$$n$$$. Since the order of $$$b$$$ must divide $$$d-1$$$, this means that the order of $$$b$$$ must be even, so output yes.

However, when I submit a solution off the above methods, I get Wrong Answer. Can anyone see what I am doing wrong? I have included my C++ code below. Thanks for the help.

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>

typedef int64_t num;

static inline num multModulo(num num1, num num2, num MOD) {
    return ( static_cast<__int128>(num1) * num2) % MOD;
}

num calcModuloExp(num base, num exp, num MOD) {
    num result = 1, cur = base;
    while (exp) {
        if (exp & 1) result = multModulo(result, cur, MOD);
        cur = multModulo(cur, cur, MOD), exp >>= 1;
    }
    return result;
}

int main() {
    num b, d;
    scanf("%" PRId64 " %" PRId64, &b, &d);
    if (d == 2) {
        puts((b & 1) ? "yes" : "no");
    } else {
        num biggestOddFactor = d-1;
        while (!(biggestOddFactor & 1)) biggestOddFactor >>= 1;
        num answer = calcModuloExp(b, biggestOddFactor, d);
        puts((answer == 1) ? "no" : "yes");
    }

    return 0;
}