競プロ典型 90 問
055 - Select 5（★2）
以下を調べればいいが、５つの掛け算でオーバーフローが起きる。
(A[i] * A[j] * A[k] * A[l] * A[m]) % P == Q
なので、掛け算を細分化し２つの掛け算を行うたびに$ $%$P $を行いオーバーフローを防ぐ。
$ A_i \cdot A_j \equiv (A_i \cdot A_j) \mathbin{\%} P \pmod{P} $
$ \Rightarrow A_i \cdot A_j \cdot A_k \cdot A_l \cdot A_m \equiv ((((A_i \cdot A_j) \mathbin{\%} P \cdot A_k) \mathbin{\%} P \cdot A_l) \mathbin{\%} P \cdot A_m) \mathbin{\%} P \pmod{P} $
従って、以下を調べればいい。
(A[i] * A[j] % P * A[k] % P * A[l] % P * A[m] % P) % P == Q
$ B = A_i \cdot A_j \mathbin{\%} P \cdot A_k \mathbin{\%} P \cdot A_l \mathbin{\%} P \cdot A_m$ と置いて、これを書き換えると
$ (B \mathbin{\%} P) \mathbin{\%} P == Q $
$ \Rightarrow B \mathbin{\%} P == Q \qquad \because B \mathbin{\%} P \equiv B \pmod{P} $
つまり、以下でもいい
A[i] * A[j] % P * A[k] % P * A[l] % P * A[m] % P == Q
ABC
108
C - Triangular Relationship
$ a+b \equiv b+c \equiv c+a \pmod{K} $
$ \Rightarrow a \equiv b \equiv c \pmod{K} \qquad \because a+b \equiv b+c \Rightarrow a \equiv c \pmod{K} \quad \text{他同様} $
$ a+b \equiv b+c \equiv c+a \equiv 0 \pmod{K} $
$ \Rightarrow 2a \equiv 2b \equiv 2c \equiv 0 \pmod{K} \qquad \because a \equiv b \equiv c \pmod{K}$
Kが奇数の場合
$ 2a \equiv 2b \equiv 2c \equiv 0 \pmod{K} $
$ \Rightarrow a \equiv b \equiv c \equiv 0 \pmod{K} \qquad \because \gcd(2,K)=1 $
例としてaを考えると、
$a = K, 2K, 3K \cdots \qquad \because a \equiv 0 \pmod{K}$
初項K, 項数n, 公差Kの等差数列の一般項は、$ An = K + (n-1)K = nK $
$An \leq N$となるnの最大値は$n=\lfloor \frac{N}{K} \rfloor$
従ってN以下の正の整数で、Kで割り切れる数の個数は、$\lfloor \frac{N}{K} \rfloor$
b,cも同様に考えると、a,b,cを$\lfloor \frac{N}{K} \rfloor$個の中から選べばよく、その組み合わせは$\lfloor \frac{N}{K} \rfloor^3 $
よって、Kが奇数の場合は、$\lfloor \frac{N}{K} \rfloor^3$
Kが偶数の場合
例としてaを考えると、
$ 2a = K, 2K, 3K, 4K, 5K, \cdots \qquad \because 2a \equiv 0 \pmod{K} $
$ \Rightarrow a = \frac{K}{2}, K, K+\frac{K}{2}, 2K, 2K+\frac{K}{2}, \cdots $
$ \therefore a \equiv 0,\frac{K}{2} \pmod{K} $
同様にして、$ a \equiv b \equiv c \equiv 0,\frac{K}{2} \pmod{K} $
$ a \equiv b \equiv c \equiv 0\pmod{K} $のとき、$\lfloor \frac{N}{K} \rfloor^3 \qquad \because \text{Kが奇数の場合参照}$
$ a \equiv b \equiv c \equiv \frac{K}{2} \pmod{K} $のとき、
例としてaを考えると、
$ a = \frac{K}{2}, \frac{K}{2}+K, \frac{K}{2}+2K \cdots \qquad \because a \equiv \frac{K}{2} \pmod{K}$
初項$\frac{K}{2}$,項数n,公差Kの等差数列の一般項は、$An = \frac{K}{2} + (n-1)K = nK - \frac{K}{2}$
$An \leq N$となるnの最大値は$ n = \lfloor \frac{N+\frac{K}{2}}{K} \rfloor $
従ってN以下の正の整数で、Kで割って$\frac{K}{2}$余る数の個数は$\lfloor \frac{N+\frac{K}{2}}{K} \rfloor$
b,cも同様に考えると、a,b,cを$\lfloor \frac{N+\frac{K}{2}}{K} \rfloor$個の中から選べばよく、その組み合わせは$\lfloor \frac{N+\frac{K}{2}}{K} \rfloor^3$
よって、Kが偶数の場合は、$\lfloor \frac{N}{K} \rfloor^3 + \lfloor \frac{N+\frac{K}{2}}{K} \rfloor^3$