ZOJ 3785 What day is that today? (费马小定理)

题目大意

今天是周六，问1^1 + 2^2 + 3^3 + … + N^N天后是周几？（1<=N<=1000000000）

解题思路

第一眼看到题目天真的以为是快速幂取模的简单应用，在飞速敲完代码看到火红的 TLE 之后意识到自己想多了，由于N的范围达到了10^9，所以快速幂取模的方法行不通。

接下来就是使用万能打表A题法，但是由于本题中的循环数太大（294）导致在眼睛看瞎之前很有可能找不到循环点（反正我是没有找到），既然打表也不靠谱，倒不如用数学的方式推导出公式。既靠谱又不伤眼睛。

首先我们关注公式中的单项 N^N % 7 的值, 当 N 的值小于7时，毫无疑问底数 N 有6种情况（1-6），当 N 的值大于7时，可以得到 N=7 * k + b, 则

（7 * k + b）^N % 7 = (7 * K+B) % 7 * (7 * K + B)^ (N-1) % 7=b * (7 * K + B) ^ (N-1) % 7 ，经过递推最终可以得到

（7 * K + B）^N % 7 = B ^ N % 7** （0<=B<=6），根据费马小定理 在 gcd (A,P)=1 的条件下存在 A ^ (P-1)=1(mod P)。

在本题中 ，N % 7 ！=0 时，恒有 B^6 % 7 = 1 ，则 B^(6*K2+B2)=B ^ B2（0<=B2<=5）。当 N % 7==0 时 ， 毫无疑问 N^N%7==0 恒成立， 则 我们可以得出一个结论 N^N % 7的数值 共有 B * B2 =6 * 7=42种情况。但是此时求出的只是单项的循环结，所以将结果再乘前缀和的循环结7即可得到最终的循环结 294 。

代码