妙用next数组打表求最小循环节len-白红宇

妙用next数组打表求最小循环节len

阅读量：6592 次

发布时间：2019-06-24

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

[数学]

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int len;int n = 1000;int next[10000];int f[50000];char s[50000];int Pow(int a, int b){    int res=1;    while(b)    {        if(b&1)            res=res*a%7;        a=a*a%7;        b>>=1;    }    return res;}void getnext(){    int j=0,k=-1;    next[0]=-1;    while(j
        
         1)      //周期大于1才是循环串        {            cout<<"ans = "<
         
          <

#include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #define ll long longusing namespace std;ll x[1005];long mod(long a,long n,long b){ //a^b mod c long t; if(n==0) return 1%b; if(n==1) return a%b; t=mod(a,n/2,b); t=t*t%b; if((n&1)==1) t=t*a%b; return t;}int main(){ string s[7]={"Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"}; x[0]=0; for(int i=1;i<=1000;++i) x[i]=(x[i-1]%7+mod(i,i,7))%7; int next[1001]; next[0] = 0; int len=1000; for(int i = 1, q = 0; i < len; i++){ //x[]里放的是要找规律的数组 while(q > 0 && x[i] != x[q]) q = next[q-1]; if (x[i] == x[q]) q++; next[i] = q; if (q != 0 && (i + 1) % (i + 1 - q) == 0){ printf("%d\n", i+1-q); //输出的就是最大循环长度 break; } } return 0;}