Hello. As some of you may know, the [Mount Allison Programming Showdown 2020](https://maps20.kattis.com/) took place yesterday, and I had a question about the [Divide and Conquer](https://maps20.kattis.com/problems/maps20.divideandconquer) 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}$. Then, it is easy to see that the order of $b$ must be $2m'$ so $b$ has even orderus, 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;↵
}↵
```
↵
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}$. Th
- - 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;↵
}↵
```
