HDU5690-All X

首先, $ F(x) $代表一个全是由数字 $ x $ 组成的 $ m $ 位数字说明了这个数字是这样组成的:$ xxxxx…x $ ,共m位。它就等于 $ x × 11111…1 $ ,共m位。所以有:
$$
F(x,m) = x \, \cdot \, \sum_{i=0}^{m-1}{10^i}
= x \, \cdot \, \frac{(10^m – 1)}{9}
$$

要使得
$$ F(x,m) \, mod \, k = c $$
只要
$$ x \, \cdot \, \frac{(10^m – 1)}{9} \, mod \, k = c $$
两边同时乘9,记得k也要扩大为原来9倍才能维持等式成立
$$ [x \, \cdot \, (10^m – 1)] \, mod \, (9k) = 9c $$
把x乘入得到
$$ (x \, \cdot \, 10^m – x) \, mod \, (9k) = 9c $$
根据$mod$运算的性质,上面的式子可以转化成
$$
\{[x \, mod \, (9k)] \cdot 10^m \, mod \, (9k)\} \, mod \, (9k) – x \, mod \, (9k) = 9c
$$
于是就可以快速幂取模了,记得开long long。

 

说点什么

avatar
  Subscribe  
提醒