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
50
  Subscribe  
提醒