当前位置: 代码迷 >> 综合 >> ZOJ3785 What day is that day?(同余与模算术)
  详细解决方案

ZOJ3785 What day is that day?(同余与模算术)

热度:6   发布时间:2024-01-16 13:43:42.0

题意:

今天星期六,求1^1+2^2……N^N天后是星期几

要点;

很明显是同余与模算术,用白书上的复杂度为O(logn)的算法。一开始我是想打表,但这题不能开数组,范围太大。后来我也想到找规律了,但我只打了30个的表,而规律从42开始,点背啊!下次注意了,打表尽量打多一点,而且注意一下排版让规律找起来比较方便。这题就是以42为一组循环,后面没问题了。


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char str[10][150] = { "Saturday","Sunday", "Monday", "Tuesday","Wednesday", "Thursday" ,"Friday" };int pow_mod(int a, int n, int m)//幂取模的模板,利用二分思想
{if (n == 0) return 1;int x = pow_mod(a, n / 2, m);long long ans = x*x%m;if (n % 2 == 1)			//如果n为奇数,说明还要乘一个aans = ans*a%m;return (int)ans;
}int main()
{int t,n,sum=0;int a[50],b[50];b[0] = 0;for (int i = 1; i <= 42; i++)//规律是以42个为1组{a[i] = pow_mod(i, i, 7);b[i] = b[i - 1] + a[i];	//第i个数前之和sum = (sum%7+a[i]%7)%7;}scanf("%d", &t);while (t--){scanf("%d", &n);int ans = (sum*(n / 42) % 7 + b[n % 42] % 7) % 7;printf("%s\n", str[ans]);}return 0;
}