fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. ll b[55]={0};
  6. void sieve()
  7.    {
  8.  
  9.     for (ll i = 2; i * i <= 50; ++i) {
  10.     if (b[i] == 0) {
  11.         for (ll j = i * i; j <= 50; j += i) {
  12.             if (b[j] == 0) {
  13.                 b[j] = i;
  14.             }
  15.         }
  16.     }
  17.    }
  18. for (ll i = 2; i <= 50; ++i) {
  19.     if (b[i] == 0) {
  20.         b[i] = i;
  21.  
  22.     }
  23. }
  24.  
  25.  
  26. }
  27. int main()
  28. {
  29.     //cout << "Hello world!" << endl;
  30.     ll t;
  31.     sieve();
  32.     cin>>t;
  33.     while(t--)
  34.     {
  35.  
  36.         ll prime[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
  37.         ll n;
  38.         cin>>n;
  39.         ll a[n+3];
  40.         for(ll i=0;i<n;i++)
  41.         {
  42.             cin>>a[i];
  43.          }
  44.         ll gd=a[0];
  45.         for(ll i=0;i<n;i++)
  46.         {
  47.             gd=__gcd(gd,a[i]);
  48.         }
  49.         //cout<<gd<<endl;
  50.         if(gd==1 || n==1)
  51.         {
  52.             cout<<0<<endl;
  53.             for(ll i=0;i<n;i++)
  54.                 cout<<a[i]<<" ";
  55.  
  56.             cout<<endl;
  57.             continue;
  58.         }
  59.  
  60.         map<ll,ll>mp;
  61.         for(ll i=0;i<n;i++)
  62.         {
  63.             ll x=a[i];
  64.             while(x!=1)
  65.             {
  66.                 mp[b[x]]++;
  67.                 x=x/b[x];
  68.             }
  69.         }
  70.         ll val;
  71.         for(ll i=0;i<15;i++)
  72.         {
  73.             if(mp[prime[i]]==0)
  74.             {
  75.                  val=prime[i];
  76.                 break;
  77.             }
  78.         }
  79.         cout<<1<<endl;
  80.         a[n-1]=val;
  81.         for(ll i=0;i<n;i++) cout<<a[i]<<" ";
  82.         cout<<endl;
  83.         mp.clear();
  84.  
  85.         //for(ll i=0;i<cnt;i++) cout<<p[i].first<<" "<<p[i].second<<endl;
  86.     }
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3A1eOX
language:
C++14 (gcc 8.3)
created:
5 years ago
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!