HDU 1452 - Happy 2004 (因子和是积性函数 + 模运算处理除法 + 快速幂取模)
题意
求出$2004^x$的因子和
思路
首先要知道因子和$\sigma (n)$是一个积性函数。
也就是说$\sigma (n) = \sigma (a) * \sigma (b) \text{, a and b are coprime.} $
那么我们把2004分解质因数
$2004^x \bmod 29 = 2^x * 3^x * 167^x \bmod 29$
所以$\sigma (2004^x) \bmod 29 = \sigma (2^x) * \sigma (3^x) * \sigma (167^x) \bmod 29$
又因为$\sigma (a^x) = 1 + a + a^2 + … + a^x = \Large \frac {a^{x+1} - 1}{x-1}$
所以结果为$ans = (2^{2n+1} - 1) * \Large \frac {3^{x+1}-1}{2} * \frac {167^{x+1}-1}{166} \normalsize \bmod 29$
对于模运算里的除法，$a / b \bmod c = a * b^{-1} \bmod c$
所以求出2和166在模29下的逆元即可。
代码
LL Quick_Mod(LL a, LL m, LL n)
{
LL ret = 1;
while (m)
{
if (m & 1) ret = ret * a % n;
a = a * a % n;
m >>= 1;
}
ret--;
return ret < 0 ? ret + n : ret;
}
int main()
{
ios::sync_with_stdio(0);
LL n;
while (cin >> n, n)
cout << Quick_Mod(2, (n<<1)+1, 29) * Quick_Mod(3, n+1, 29) * Quick_Mod(22, n+1, 29) * 9 % 29 << endl;
}