Ideone.com

fork download

copy

#include <cstdio>
#include <cstring>
const int N=105;
int T,n;
int a[N];
int mat[N][N];
bool prime[N*N];
int List[N*N];
 
void init(){
    int i,j;
    memset(prime,true,sizeof(prime));
    for (i=2;i<=10000;i++)
      for (j=i+i;j<=10000;j+=i)
        prime[j]=false;
    int cnt=0;
    for (i=2;i<=10000;i++)
      if (prime[i]) List[++cnt]=i;
}
 
int Num[65];
 
void output(int cf){
    memset(Num,0,sizeof(Num));
    Num[0]=1;
    for (int k=1;k<=cf;k++){
        for (int i=0;i<60;i++) Num[i]*=2;
        for (int i=0;i<60;i++){
            Num[i+1]+=Num[i]/10;
            Num[i]%=10;
        }
    }
    Num[0]--;
    for (int i=0;Num[i]<0;i++){
        Num[i]+=10;
        Num[i+1]--;
    }
    int i;
    for (i=60;i>=1;i--) if (Num[i]!=0) break;
    for (;i>=0;i--) printf("%d",Num[i]);
    puts("");
}
 
template <class T> inline void swap(T &x,T &y){ T tmp=x; x=y; y=tmp; }
 
void solve(){
    int cut,i,j,k,now=1;   //now表示当前主元
    cut=1;
    while (now<=n && cut<=T){
        bool check=false;
        while (now<=n && cut<=T && !check){
            for (i=cut;i<=T;i++)
              if (mat[i][now]){
                  check=true;
                  k=i;
                  break;
              }
            if (check){
                for (j=1;j<=n;j++)
                  swap(mat[k][j],mat[cut][j]);
                for (i=cut+1;i<=T;i++)
                  if (mat[i][now])
                    for (j=now;j<=n;j++)
                      mat[i][j]^=mat[cut][j];
                cut++;
            }
            now++;
        }
    }
    cut--;
    output(n-cut);
}
 
int main(){
    init();
    int Tc,i,j;
    for (scanf("%d",&Tc);Tc;Tc--){
        scanf("%d%d",&T,&n);
        memset(mat,0,sizeof(mat));
        for (i=1;i<=n;i++){
          scanf("%d",&a[i]);
          for (j=1;j<=T;j++)
            if (a[i]%List[j]==0){
                int tmp=a[i],cnt=0;
                while (tmp%List[j]==0){tmp/=List[j]; cnt++;}
                if (cnt&1) mat[j][i]=1;
            }
        }
        solve();
        if (Tc>1) puts("");
    }
}

I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdHJpbmc+CmNvbnN0IGludCBOPTEwNTsKaW50IFQsbjsKaW50IGFbTl07CmludCBtYXRbTl1bTl07CmJvb2wgcHJpbWVbTipOXTsKaW50IExpc3RbTipOXTsKCnZvaWQgaW5pdCgpewogICAgaW50IGksajsKICAgIG1lbXNldChwcmltZSx0cnVlLHNpemVvZihwcmltZSkpOwogICAgZm9yIChpPTI7aTw9MTAwMDA7aSsrKQogICAgICBmb3IgKGo9aStpO2o8PTEwMDAwO2orPWkpCiAgICAgICAgcHJpbWVbal09ZmFsc2U7CiAgICBpbnQgY250PTA7CiAgICBmb3IgKGk9MjtpPD0xMDAwMDtpKyspCiAgICAgIGlmIChwcmltZVtpXSkgTGlzdFsrK2NudF09aTsKfQoKaW50IE51bVs2NV07Cgp2b2lkIG91dHB1dChpbnQgY2YpewogICAgbWVtc2V0KE51bSwwLHNpemVvZihOdW0pKTsKICAgIE51bVswXT0xOwogICAgZm9yIChpbnQgaz0xO2s8PWNmO2srKyl7CiAgICAgICAgZm9yIChpbnQgaT0wO2k8NjA7aSsrKSBOdW1baV0qPTI7CiAgICAgICAgZm9yIChpbnQgaT0wO2k8NjA7aSsrKXsKICAgICAgICAgICAgTnVtW2krMV0rPU51bVtpXS8xMDsKICAgICAgICAgICAgTnVtW2ldJT0xMDsKICAgICAgICB9CiAgICB9CiAgICBOdW1bMF0tLTsKICAgIGZvciAoaW50IGk9MDtOdW1baV08MDtpKyspewogICAgICAgIE51bVtpXSs9MTA7CiAgICAgICAgTnVtW2krMV0tLTsKICAgIH0KICAgIGludCBpOwogICAgZm9yIChpPTYwO2k+PTE7aS0tKSBpZiAoTnVtW2ldIT0wKSBicmVhazsKICAgIGZvciAoO2k+PTA7aS0tKSBwcmludGYoIiVkIixOdW1baV0pOwogICAgcHV0cygiIik7Cn0KCnRlbXBsYXRlIDxjbGFzcyBUPiBpbmxpbmUgdm9pZCBzd2FwKFQgJngsVCAmeSl7IFQgdG1wPXg7IHg9eTsgeT10bXA7IH0KCnZvaWQgc29sdmUoKXsKICAgIGludCBjdXQsaSxqLGssbm93PTE7ICAgLy9ub3fooajnpLrlvZPliY3kuLvlhYMKICAgIGN1dD0xOwogICAgd2hpbGUgKG5vdzw9biAmJiBjdXQ8PVQpewogICAgICAgIGJvb2wgY2hlY2s9ZmFsc2U7CiAgICAgICAgd2hpbGUgKG5vdzw9biAmJiBjdXQ8PVQgJiYgIWNoZWNrKXsKICAgICAgICAgICAgZm9yIChpPWN1dDtpPD1UO2krKykKICAgICAgICAgICAgICBpZiAobWF0W2ldW25vd10pewogICAgICAgICAgICAgICAgICBjaGVjaz10cnVlOwogICAgICAgICAgICAgICAgICBrPWk7CiAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKGNoZWNrKXsKICAgICAgICAgICAgICAgIGZvciAoaj0xO2o8PW47aisrKQogICAgICAgICAgICAgICAgICBzd2FwKG1hdFtrXVtqXSxtYXRbY3V0XVtqXSk7CiAgICAgICAgICAgICAgICBmb3IgKGk9Y3V0KzE7aTw9VDtpKyspCiAgICAgICAgICAgICAgICAgIGlmIChtYXRbaV1bbm93XSkKICAgICAgICAgICAgICAgICAgICBmb3IgKGo9bm93O2o8PW47aisrKQogICAgICAgICAgICAgICAgICAgICAgbWF0W2ldW2pdXj1tYXRbY3V0XVtqXTsKICAgICAgICAgICAgICAgIGN1dCsrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIG5vdysrOwogICAgICAgIH0KICAgIH0KICAgIGN1dC0tOwogICAgb3V0cHV0KG4tY3V0KTsKfQoKaW50IG1haW4oKXsKICAgIGluaXQoKTsKICAgIGludCBUYyxpLGo7CiAgICBmb3IgKHNjYW5mKCIlZCIsJlRjKTtUYztUYy0tKXsKICAgICAgICBzY2FuZigiJWQlZCIsJlQsJm4pOwogICAgICAgIG1lbXNldChtYXQsMCxzaXplb2YobWF0KSk7CiAgICAgICAgZm9yIChpPTE7aTw9bjtpKyspewogICAgICAgICAgc2NhbmYoIiVkIiwmYVtpXSk7CiAgICAgICAgICBmb3IgKGo9MTtqPD1UO2orKykKICAgICAgICAgICAgaWYgKGFbaV0lTGlzdFtqXT09MCl7CiAgICAgICAgICAgICAgICBpbnQgdG1wPWFbaV0sY250PTA7CiAgICAgICAgICAgICAgICB3aGlsZSAodG1wJUxpc3Rbal09PTApe3RtcC89TGlzdFtqXTsgY250Kys7fQogICAgICAgICAgICAgICAgaWYgKGNudCYxKSBtYXRbal1baV09MTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBzb2x2ZSgpOwogICAgICAgIGlmIChUYz4xKSBwdXRzKCIiKTsKICAgIH0KfQ==

Runtime error #stdin compilation error #stdout 0.08s 2824KB

stdin

copy

Standard input is empty

compilation info

prog.cpp: In function ‘int main()’:
prog.cpp:77: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:78: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:81: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

stdout

copy

https://ideone.com/I5M1q

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language