首先，把P进行质因数分解，每一个不用的质因数压成1位

f[i][j]表示1前i位用j“拥有”的质因数表示。

然后都懂得。。。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

#include<cmath>

#include<cctype>

#include<cassert>

#include<climits>

using namespace std;

#define For(i,n) for(int i=1;i<=n;i++)

#define Rep(i,n) for(int i=0;i<n;i++)

#define Fork(i,k,n) for(int i=k;i<=n;i++)

#define ForD(i,n) for(int i=n;i;i--)

#define Forp(x) for(int p=pre[x];p;p=next[p])

#define RepD(i,n) for(int i=n;i>=0;i--)

#define MEM(a) memset(a,0,sizeof(a))

#define MEMI(a) memset(a,127,sizeof(a))

#define MEMi(a) memset(a,128,sizeof(a))

#define INF (2139062143)

#define F (1000000009)

#define MAXN (1000+10)

#define MAXM (1000+10)

typedef long long ll;

int T,n,P,p[MAXN],m,a[MAXN],s[MAXN],w[MAXN][MAXN],bin[MAXN],f[MAXN][MAXM];

int main()

{

   freopen("CF-2013CTS01E04-challenge.in","r",stdin);

   cin>>T;

   bin[1]=1;Fork(i,2,30) bin[i]=bin[i-1]<<1;

// For(i,30) cout<<bin[i]<<' ';

   while(T--)

   {

      cin>>n>>P;m=0;

      int P2=P;

      Fork(i,2,sqrt(P))

         if (P%i==0)

         {

            P/=i;

            p[++m]=i;

         }

      if (P) p[++m]=P;

      P=P2;

      s[0]=0; For(i,n) cin>>a[i],s[i]=s[i-1]+a[i];

      //For(i,m) cout<<p[i]<<' ';cout<<endl;

//    memset(w,0,sizeof(w));

      For(i,n)

         Fork(j,i,n)

         {

            w[i][j]=0;

            int t=s[j]-s[i-1];

            For(k,m)

               if (t%p[k]==0) w[i][j]|=bin[k];

         }

      MEMI(f);

//    cout<<w[2][2]<<endl;

      For(i,n)

         Rep(j,bin[m+1])

         {

            if ((w[1][i]&j)==j) f[i][j]=min(f[i][j],0);

            Fork(k,i+1,n)

            {

               f[k][w[i+1][k]|j]=min(f[k][w[i+1][k]|j],f[i][j]+1);

            }

         }

      int ans=1,mincut=0;

      Rep(i,bin[m+1])

      {

         int t=1;

         For(k,m) if (bin[k]&i) t*=p[k];

         if (t>ans&&f[n][i]^INF)

         {

            ans=t;mincut=f[n][i];

         }

      }

      cout<<ans<<' '<<mincut<<endl;

   }

   while(1);

   return 0;

}