今天是星期六。求經過 S = 1^1 + 2^2 + ... + N^N 天後是星期幾。N ≤ 109，多測試用例。
星期循環週期 7。需計算 S mod 7。觀察 i^i mod 7 的序列：
i mod 7 週期 7i mod 6 決定冪次模 7（費馬小定理：a^6 ≡ 1 (mod 7) 對 7∤a）lcm(7, 6) = 42？實際驗證 i^i mod 7 週期為 42？不，代碼中用 294 = 7 × 42？經測試/打表發現：i^i mod 7 序列週期為 294（= 7 × 6 × 7？實際為 lcm(7, φ(7)) × 7？）。前綴和 S(N) mod 7 也週期 294。
int period = 294;
int sum[period+1];
sum[0] = 0;
for (int i=1; i<=period; ++i) {
int p = 1;
for (int j=0; jday = sum[N % period]，映射到星期名稱：0:Saturday, 1:Sunday, ..., 6:Friday。
#include
const char* day[7] = {"Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"};
int sum[295];
int powmod(int a, int n, int mod) {
int r = 1;
while (n) {
if (n&1) r = r*a % mod;
a = a*a % mod;
n >>= 1;
}
return r;
}
int main() {
sum[0] = 0;
for (int i=1; i<=294; ++i) {
sum[i] = (sum[i-1] + powmod(i, i, 7)) % 7;
}
int T; scanf("%d", &T);
while (T--) {
long long N; scanf("%lld", &N);
printf("%s\n", day[sum[N % 294]]);
}
return 0;
}
週期 294 = 7 × 42。因 a^b mod 7 依賴 a mod 7 和 b mod 6（對 a≢0）。i mod 7 週期 7，i mod 6 週期 6，合成週期 42。但 i≡0 (mod 7) 時 i^i ≡ 0，需額外考慮。實際最小週期為 294 = 7 × 42。
