Calculation date (fast power + tabulation)

Title:
Today's Saturday, 11 + 22 What day of the week is in N^N days

Train of thought:
For congruence and modular arithmetic, a fast power modular algorithm is used, and the time complexity is O(logn).

1. Use the fast power to find 1 ^ 1, 2 ^ 2 +, 3 ^ 3 N^N
It is found that the length of the cycle section is 42, i.e
(11)%7=(4343)%7,
(22)%7=(4444)%7,
(33)%7=(4545)%7,
(n^n)%7=( (42+n)^(42+n) )%7
2. Then hit the table to find (n^n)%7 of each number N in [1,42] interval, and then find the prefix of array a and array b,

Sum refers to the number of days contributed by a circular section, that is sum = (1 ^ 1 + 3 ^ 3 + 41^41 + 42^42)%7=6;
For each sample n, direct calculation is enough

```#include <math.h>
#include <stdio.h>
char chars[7][10] = {"Saturday",  "Sunday",   "Monday", "Tuesday",
"Wednesday", "Thursday", "Friday"};
// Fast multiplication is similar to fast power
int qmul(int a, int b, int mod) {
int ans = 0;
while (b) {
if (b & 1) {
ans = (ans + a) % mod;
}
b >>= 1;
a = (a << 1) % mod;
}
return ans;
}
// Realize fast power
int qpow(int a, int n, int mod) {
int res = 1;
while (n) {
if (n & 1) {
// Prototype is res = res * a% Mod
res = qmul(res, a, mod) % mod;
}
n >>= 1;
// Prototype a = a * a% Mod
a = qmul(a, a, mod) % mod;
}
return res;
}

// a[n] means n*n%7
int a[50];
// b[n] means a[1]+a[2]+a[3]...a[n]
int b[50];

int main() {
b[0] = 0;
for (int i = 1; i <= 42; i++) {
a[i] = qpow(i, i, 7);
b[i] = b[i - 1] + a[i];
}
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int sum = b[42] % 7;
// Total days of a cycle
// Number of cycle sections
int num = n / 42;
int ans = ((sum * num) % 7 + b[n % 42] % 7) % 7;
printf("%s", chars[ans]);
}
return 0;
}
```

Another way to find sum

```for (int i = 1; i <= 42; i++) //Cycle section 42
{
a[i] =qpow(i, i, 7);
b[i] = b[i - 1] + a[i];
sum = (sum % 7 + a[i] % 7) % 7; //Key understanding
}

```

Posted on Tue, 05 Nov 2019 12:09:38 -0800 by Matt Parsons