洛谷题目: B2074
1. 模 mod 是什么？
本质：只关心余数，不关心商
例如:
9 \pmod 2=1
即 9/2等于4余1
9/2=4...1
2. 乘法的模运算性质
a×b \pmod c=((a\pmod c)×(b\pmod c))\pmod c
这里可以分多个部分来理解
首先是a*b\pmod c ，这部分是求a*b的积，再取余数，等于接下来的a \pmod c (a取余数) 乘 b \pmod c (b取余数) ，这个整体再取一次余数。
a*b\pmod c = [a \pmod c * b \pmod c] \pmod c
3. 题目分析
如果算a的b次方再取余，按照数据范围，最大数可达100的10000次方，不可行。这样可以用到以上的性质
a^b \bmod 7
= (a \cdot a \cdot a \cdots a)_b \bmod 7\\
= \bigl((a \bmod 7)\cdot(a \bmod 7)\cdots(a \bmod 7)\bigr)\bmod 7\\
= \bigl((a \bmod 7)^b\bigr)\bmod 7\\
= \bigl((a \bmod 7)^{\,b \bmod 6}\bigr)\bmod 7
用测试数据代入\bigl((a \bmod 7)^{\,b \bmod 6}\bigr)\bmod 7得
\bigl((3 \bmod 7)^{\,2000 \bmod 6}\bigr)\bmod 7\\
=3^2 \pmod7\\
=2
结果为2，是星期二
代码：URL