題意：(1^1 + 2^2 + 3^3+……+N^N )%7

方法一：此題可找循環節以294為循環節點；

方法二：運用二分求等比數列&&快速冪

上式可以轉化： 1^1 + 1^8 +1^15+……+1^(1+7*k) = 1^1( (1^7)^0+ (1^7)^2+……+(1^7)^k)求公比為1^7的等比數列前k項和

同理：求出以2^7、3^7、4^7、5^7、6^7為公比等比數列前k項和

方法一代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<stack> #include<algorithm> using namespace std; const int mod = 7; int a[300]={0}; char str[10][10] = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"}; int fast_pow(int a,int n) {int ans = 1;while(n){if(n&1)ans = ans * a%mod;a = a*a %mod;n /= 2;}return ans; } void init() {int sum = 0;for(int i = 1;i <= 294;i++){int k = fast_pow(i,i);sum = (sum + k) % 7;if(sum == 0) sum = 7;a[i] = sum - 1;}a[0] = a[294]; } int main() {int N,T;init();scanf("%d",&T);while(T--){scanf("%d",&N);printf("%s\n",str[a[N%294]]);}return 0; }

方法二代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<stack> #include<algorithm> using namespace std; const int mod = 7; char str[10][10] = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"}; int fast_pow(int a,int n) {int ans = 1;while(n){if(n&1)ans = ans * a%mod;a = a*a %mod;n /= 2;}return ans; } int fun(int a,int b) {int s,t;if(b==0) return 0;if(b==1) return a%mod;s=fun(a,b/2)%mod;if(b&1){t=fast_pow(a,b/2+1)%mod;return (s*(t+1)+t)%mod;}else{t=fast_pow(a,b/2)%mod;return (s*(t+1))%mod;} } int main() {int N,T;scanf("%d",&T);while(T--){scanf("%d",&N);int t = N / 7;int sum = 0,ans = 0;if(t > 0){for(int i = 1; i < 7; i++){int w = fast_pow(i,7);int x = fast_pow(i,i);ans = (1 + fun(w,t-1))%mod;ans = ans * x % mod;sum = (sum + ans)%mod;}}for(int i = t * 7 + 1; i<=N; i++)sum = (sum + fast_pow(i%mod,i))%mod;if(sum == 0) sum = 7;sum -= 1;printf("%s\n",str[sum]);}return 0; }

總結

以上是生活随笔為你收集整理的zoj-What day is that day?的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。