zoj-What day is that day?-白红宇

zoj-What day is that day?

阅读量：4286 次

发布时间：2019-05-27

本文共 1857 字，大约阅读时间需要 6 分钟。

题意：(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
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         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
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         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;}