Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### Noble_Mushtak's blog

By Noble_Mushtak, history, 2 months ago, ,

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;
}


• +3

 » 2 months ago, # |   0 Auto comment: topic has been updated by Noble_Mushtak (previous revision, new revision, compare).
 » 2 months ago, # |   +5 You seemed to miss the case when there is no multiplicative order. ($d|b$)
•  » » 2 months ago, # ^ |   0 OK, I changed it so it outputs no when $b^n\equiv 0\pmod{d}$ and my solution got Accepted. Thanks for all the help!
 » 2 months ago, # |   +5 You missed the case where $b$ is not a unit modulo $d$ (i.e. $d\mid b$).