fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ld long double
  5. #define all(x) (x).begin(), (x).end()
  6. #define debug(x) cerr << #x << " = " << (x) << endl;
  7. const int MOD = 1e9 + 7;
  8. const int INF = 1e18;
  9. const ld PI = acos(-1.0);
  10. int gcd(int a,int b){return b?gcd(b,a%b):a;}
  11. int lcm(int a,int b){return a/gcd(a,b)*b;}
  12. void solve(){
  13.     int n;cin>>n;
  14.     vector<int>arr(n),b(n);
  15.     for(int i=0;i<n;i++)cin>>arr[i];
  16.     for(int i=0;i<n;i++)cin>>b[i];
  17.     unordered_map<int,int>factors;
  18.     int maxi=0,largest_num=0,freq_even=0;
  19.     for(int i=0;i<n;i++){
  20.         if(arr[i]%2==0) freq_even++;
  21.         bool hasFactor=false;
  22.         for(int j=2;j*j<=arr[i];j++){
  23.             if(arr[i]%j==0){
  24.                 hasFactor=true;
  25.                 int fact1=j; int fact2=arr[i]/j;
  26.                 if(fact1==fact2) factors[fact1]++;
  27.                 else{
  28.                     factors[fact1]++;
  29.                     factors[fact2]++;
  30.                 }
  31.                 if(factors[fact1]>=maxi){
  32.                     largest_num=fact1;
  33.                     maxi=factors[fact1];
  34.                 }
  35.                 if(factors[fact2]>=maxi){
  36.                     largest_num=fact2;
  37.                     maxi=factors[fact2];
  38.                 }
  39.             }
  40.         }
  41.         if(!hasFactor&&arr[i]>1){
  42.             factors[arr[i]]++;
  43.             if(factors[arr[i]]>=maxi){
  44.                 largest_num=arr[i];
  45.                 maxi=factors[arr[i]];
  46.             }
  47.         }
  48.     }
  49.     if(maxi>=2){
  50.         cout<<0<<endl;
  51.         return;
  52.     }
  53.     if(freq_even==1){
  54.         cout<<1<<endl;
  55.         return;
  56.     }
  57.     for(int i=0;i<n;i++){
  58.         int prev=arr[i];
  59.         bool hasFactor=false;
  60.         for(int j=2;j*j<=prev;j++){
  61.             if(prev%j==0){
  62.                 hasFactor=true;
  63.                 int fact1=j,fact2=prev/j;
  64.                 if(fact1==fact2) factors[fact1]--;
  65.                 else{
  66.                     factors[fact1]--;
  67.                     factors[fact2]--;
  68.                 }
  69.             }
  70.         }
  71.         if(!hasFactor&&prev>1) factors[prev]--;
  72.  
  73.         int curr=arr[i]+1;
  74.         maxi=0;
  75.         largest_num=0;
  76.         bool currHasFactor=false;
  77.         for(int j=2;j*j<=curr;j++){
  78.             if(curr%j==0){
  79.                 currHasFactor=true;
  80.                 int fact1=j; 
  81.                 int fact2=curr/j;
  82.                 if(fact1==fact2) factors[fact1]++;
  83.                 else{
  84.                     factors[fact1]++;
  85.                     factors[fact2]++;
  86.                 }
  87.                 if(factors[fact1]>=maxi){
  88.                     largest_num=fact1;
  89.                     maxi=factors[fact1];
  90.                 }
  91.                 if(factors[fact2]>=maxi){
  92.                     largest_num=fact2;
  93.                     maxi=factors[fact2];
  94.                 }
  95.             }
  96.         }
  97.  
  98.         if(!currHasFactor&&curr>1){
  99.             factors[curr]++;
  100.             if(factors[curr]>=maxi){
  101.                 largest_num=curr;
  102.                 maxi=factors[curr];
  103.             }
  104.         }
  105.  
  106.         if(maxi>=2){
  107.             cout<<1<<endl;
  108.             return;
  109.         }
  110.  
  111.         for(int j=2;j*j<=curr;j++){
  112.             if(curr%j==0){
  113.                 int fact1=j;
  114.                 int fact2=curr/j;
  115.                 if(fact1==fact2) factors[fact1]--;
  116.                 else{
  117.                     factors[fact1]--;
  118.                     factors[fact2]--;
  119.                 }
  120.             }
  121.         }
  122.  
  123.         if(!currHasFactor&&curr>1) factors[curr]--;
  124.  
  125.         for(int j=2;j*j<=prev;j++){
  126.             if(prev%j==0){
  127.                 int fact1=j;
  128.                 int fact2=prev/j;
  129.                 if(fact1==fact2)factors[fact1]++;
  130.                 else{
  131.                     factors[fact1]++;
  132.                     factors[fact2]++;
  133.                 }
  134.             }
  135.         }
  136.  
  137.         if(!hasFactor&&prev>1) factors[prev]++;
  138.     }
  139.     cout<<2<<endl;
  140. }
  141. int32_t main(){
  142.     ios::sync_with_stdio(false);
  143.     cin.tie(nullptr);
  144.     int t=1;cin>>t;
  145.     while(t--){solve();}
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6
2
1 1
1 1
2
4 8
1 1
5
1 1 727 1 1
1 1 1 1 1
2
3 11
1 1
3
2 7 11
1 1 1
3
7 12 13
1 1 1
stdout
copy 
2
0
2
1
1
1
https://ideone.com/1jPHIQ
language:
C++14 (gcc 8.3)
created:
7 days 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!