n!最末尾非0数

最小周期串：
如果s是ss的周期串，那么ss就可以表示成几个周期的s,
如果s是ss的最小周期串，那么s就是ss的周期串中最小的一个.
例，ZgxZgxZgxZgx的最小周期串是Zgx.
{很好理解}

给你一串数字ss，找出它的最小周期串n，求n!十进制表示的最末尾的非零数。ss的长度小于等于100。

 /*

 朴素版

 */

 #include<iostream>

 #include<string>

 using namespace std;

 string s;

 int len=,i;

 int sum2=;

 int ans=;

 int a[]={,,,,,,,};

 //g(n)=1*3*5*7*9....*(2*n-1)

 int g(int n){

     if(n==) return a[];

     if(n==) return a[];

     sum2-=(n+)/;   //2的指数减去5的指数 

     return (g((n+)/)*a[(n-(n+)/-)%])%;

     }

 //f(n)=n!

 int f(int n){

     if(n==) return ;

     sum2+=n/;   //加上2的指数 

     return (f(n/)*g(n-n/))%;

     }

 int main()

 {

     cin>>s;

     for(len=;len<=s.size();len++)

     if(s.size()%len==)

     {

        for(i=;i<s.size();++i)

        if(s[i%len]!=s[i]) break;

        if(i>=s.size()) break;

                }

     int n=;

     for(i=;i<len;++i)

     n=n*+s[i]-'';

     ans=f(n);

     while(sum2>)

     {

       sum2--;

       ans*=;

       ans%=;

                  }

     while(sum2<)

     {

       sum2++;

       ans*=;

       ans%=;

                  }

     cout<<ans<<endl;                

  //   system("pause");

     }

 /*

 高精度版

 */

 #include<iostream>

 #include<string>

 using namespace std;

 string s;

 int len=,i;

 int sum2[]={};

 int num[]={};

 int ans=;

 int a[]={,,,,,,,};

 int b[]={,,,};

 void print(int x[]){

      int i=;

      for(i=;i>=;i--)

      if(x[i]!=) break;

      cout<<endl;

      while(i>=) cout<<x[i--];

      cout<<endl;

      }

 //return x==t

 bool Equal(int x[],int t){

      for(int i=;i>;i--)

      if(x[i]!=) return false;

      if(x[]==t) return true;

      return false;

      }

 //z=y+t

 void add(int z[],int y[],int t){

      for(int i=;i<=;++i)

      z[i]=y[i];

      z[]+=t;

      int i=;

      while(z[i]>=)

      {

        z[i+]+=z[i]/;

        z[i]%=;

        i++;

                    }

      return ;

      }

 //x=x-y

 void Sub(int x[],int y[]){

      for(int i=;i<=;++i)

      {

        x[i]=x[i]-y[i];

        if(x[i]<) {x[i]+=;x[i+]-=;}

              }

      return ;

      }

 //return (x-y-t)%m

 int SubAndMod(int x[],int y[],int t,int m){

     Sub(x,y);

     x[]-=t;

     int i=;

     while(x[i]<)

     {

       x[i]+=;

       x[i+]-=;

       i++;

                  }

     int tt=;

     for(int i=;i>=;i--)

     {

        tt=tt*;

        tt=(tt+x[i])%m;

             }

     return tt;

     }

 //y=x/k

 void Divide(int y[],int x[],int k){

      int t=;

      for(int i=;i>=;i--)

      {

        y[i]=(t+x[i])/k;

        t=(t+x[i])%k;

        t*=;

              }

      }

 //g(x)=1*3*5*7*9....*(2*x-1)

 int g(int x[]){

     if(Equal(x,)) return a[];

     if(Equal(x,)) return a[];

     int y[]={},z[]={};

     add(y,x,);    //y=x+2

     Divide(z,y,); //z=y/5  z为5的指数

     Sub(sum2,z);   //2的指数减去5的指数 

     int t=SubAndMod(x,z,,);   //t=(x-(x+2)/5-1)%8

     return (g(z)*a[t])%;

     }

 //y=y+x

 void Sum(int y[],int x[]){

      for(int i=;i<=;++i)

      {

        y[i]=y[i]+x[i];

        y[i+]+=y[i]/;

        y[i]%=;

              }

      }

 //f(x)=x!

 int f(int x[]){

     if(Equal(x,)) return ;

     int y[]={};

     Divide(y,x,);   //y=x/2

     Sum(sum2,y);     //加上2的指数

     if(x[]%==) return (f(y)*g(y))%;

     int z[]={};

     add(z,y,);

     return (f(y)*g(z))%;

     }

 int main()

 {

     cin>>s;

     for(len=;len<=s.size();len++)

     if(s.size()%len==)

     {

        for(i=;i<s.size();++i)

        if(s[i%len]!=s[i]) break;

        if(i>=s.size()) break;

                }

     for(i=;i<len;++i)

     num[i]=s[len-i-]-'';

     ans=f(num);

     int z[]={};

     if(!Equal(sum2,))

     ans=ans*b[SubAndMod(sum2,z,,)];

     ans%=;

     cout<<ans<<endl;

   //  system("pause");

     }

巴特西

n!最末尾非0数

最新文章

热门文章