UVA 10061 - How many zero's and how many digits ?

UVA 10061 - How many zero's and how many digits ?

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1002

題目概述:

給數字N,B。求N!在B進位下有多少個後導0與有多少位數。

思路:

待補QQ

AC Code:

//By SCJ

#include<iostream>

#include<cmath>

#include<vector>

//#include<bits/stdc++.h>

using namespace std;

#define INF 1000000000

#define endl '\n'

bool np[800];

vector<int> p;

struct P{

   int x,time;

};

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

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

   {

       if(!np[i]){

           p.push_back(i);

           for(int j=i*i;j<800;j+=i) np[j]=1;

       }

   }

   int n,b;

   while(cin>>n>>b)

   {

       vector<P> bp;

       int tp=b,t;

       for(int i:p)

       {

           t=0;

           while(tp%i==0) tp/=i,t++;

           if(t) bp.push_back({i,t});

           if(!tp) break;

       }

       int ans1=INF;

       double ans2=0;

       for(P i:bp)

       {

           tp=n;t=0;

           while(tp) t+=tp/i.x,tp/=i.x;

           if(t) ans1=min(ans1,t/i.time);

           else ans1=0;

       }

       for(int i=1;i<=n;++i) ans2+=log(i)/log(b);

       cout<<ans1<<' '<<(int)ans2+1<<endl;

   }

}

POJ 3734 Blocks

POJ 3734 Blocks

題目概述:腦書p.205

有n個格子，有紅、藍、綠、黃 四種顏色可以塗，每一個只能塗一種顏色。請問將紅色與綠色都塗在偶數個格子上的方法總數。

思路:

利用矩陣快速冪。

狀態為(紅和綠皆為偶數，紅和綠其一為奇數，紅和綠皆為奇數)。

轉移矩陣就看code吧~

AC code:

//By SCJ

#include<iostream>

#include<vector>

using namespace std;

#define endl '\n'

#define MOD 10007

typedef long long ll;

typedef vector<int> vec;

typedef vector<vec> mat;

mat mul(mat &A,mat &B)

{

   mat C(A.size(),vec(B[0].size()));

   for(int i=0;i<A.size();++i)

       for(int j=0;j<B[0].size();++j)

           for(int k=0;k<B.size();++k)

               C[i][j]=(C[i][j]+A[i][k]*B[k][j]%MOD)%MOD;

   return C;

}

mat POW(mat A,int n)

{

   mat res(A.size(),vec(A.size()));

   for(int i=0;i<A.size();++i) res[i][i]=1;

   mat base=A;

   while(n)

   {

       if(n&1) res=mul(base,res);

       base=mul(base,base);

       n>>=1;

   }

   return res;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   mat P(3,vec(3));

   P[0][0]=2;P[0][1]=1;P[0][2]=0;

   P[1][0]=2;P[1][1]=2;P[1][2]=2;

   P[2][0]=0;P[2][1]=1;P[2][2]=2;

   int T;cin>>T;

   while(T--)

   {

       int n;cin>>n;

       cout<<POW(P,n)[0][0]<<endl;

   }

}