題目大意

今天是周六，問(wèn)1^1 + 2^2 + 3^3 + … + N^N天后是周幾？（1<=N<=1000000000）

解題思路

第一眼看到題目天真的以為是快速冪取模的簡(jiǎn)單應(yīng)用，在飛速敲完代碼看到火紅的 TLE 之后意識(shí)到自己想多了，由于N的范圍達(dá)到了10^9，所以快速冪取模的方法行不通。

接下來(lái)就是使用萬(wàn)能打表A題法，但是由于本題中的循環(huán)數(shù)太大（294）導(dǎo)致在眼睛看瞎之前很有可能找不到循環(huán)點(diǎn)（反正我是沒(méi)有找到），既然打表也不靠譜，倒不如用數(shù)學(xué)的方式推導(dǎo)出公式。既靠譜又不傷眼睛。

首先我們關(guān)注公式中的單項(xiàng) N^N % 7 的值, 當(dāng) N 的值小于7時(shí)，毫無(wú)疑問(wèn)底數(shù) N 有6種情況（1-6），當(dāng) N 的值大于7時(shí)，可以得到 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 ，經(jīng)過(guò)遞推最終可以得到

（7 * K + B）^N % 7 = B ^ N % 7** （0<=B<=6），根據(jù)費(fèi)馬小定理 在 gcd (A,P)=1 的條件下存在 A ^ (P-1)=1(mod P)。

在本題中 ，N % 7 ！=0 時(shí)，恒有 B^6 % 7 = 1 ，則 B^(6*K2+B2)=B ^ B2（0<=B2<=5）。當(dāng) N % 7==0 時(shí) ， 毫無(wú)疑問(wèn) N^N%7==0 恒成立， 則 我們可以得出一個(gè)結(jié)論 N^N % 7的數(shù)值 共有 B * B2 =6 * 7=42種情況。但是此時(shí)求出的只是單項(xiàng)的循環(huán)結(jié)，所以將結(jié)果再乘前綴和的循環(huán)結(jié)7即可得到最終的循環(huán)結(jié) 294 。

代碼