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