fork download
copy 
  1. // #include<debugger.h>
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. // #include<ext/pb_ds/assoc_container.hpp>
  7. // using namespace __gnu_pbds;
  8.  
  9. #define int long long
  10. // typedef long long ll;
  11. // typedef tree< int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
  12.  
  13. #define endl '\n'
  14. #define mem(a,b) memset(a, b, sizeof(a))
  15. #define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  16. #define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
  17. #define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  18.  
  19. #define MOD 1000000007
  20. const double PI = acos(-1);
  21. const double eps = 1e-9;
  22.  
  23. const int MX = 2e5 + 10;
  24. bitset<MX> isPrime;
  25. vector<int> lowestPrime(MX, 0);
  26.  
  27. void sieve() 
  28. { 
  29.     for (int i = 3; i < MX; i += 2) isPrime[i] = 1; 
  30.  
  31.     for (int i = 3; i < MX; i += 2) { 
  32.         if (isPrime[i] == 1) {
  33.             lowestPrime[i] = i;
  34.             for (int j = i*i; j < MX; j += (i + i)) { 
  35.                 isPrime[j] = 0;
  36.                 if (lowestPrime[j] == 0)
  37.                     lowestPrime[j] = i; 
  38.             } 
  39.         } 
  40.     } 
  41.  
  42.     isPrime[2] = 1;
  43.     for (int i = 2; i < MX; i += 2)
  44.         lowestPrime[i] = 2;
  45. } 
  46.  
  47. vector<int> factorization(int n) {
  48.     vector<int> ret; 
  49.  
  50.     while (n > 1) { 
  51.         int p = lowestPrime[n]; 
  52.  
  53.         if (n % p == 0)
  54.             ret.push_back(p);
  55.  
  56.         while (n % p == 0) { 
  57.             n /= p; 
  58.         } 
  59.     } 
  60.  
  61.     return ret; 
  62. }
  63.  
  64. void solve(int ti)
  65. {
  66.     int n;
  67.     cin >> n;
  68.  
  69.     vector<int> a(n), b(n);
  70.     for (int &x : a)
  71.         cin >> x;
  72.  
  73.     for (int &x : b)
  74.         cin >> x;
  75.  
  76.     set<int> st;
  77.     for (int i = 0; i < n; i++) {
  78.         if (a[i] == 1) continue;
  79.  
  80.         vector<int> ret = factorization(a[i]);
  81.         for (int x : ret) {
  82.             if (!st.empty() and st.find(x) != st.end()) {
  83.                 cout << 0 << endl;
  84.                 return;
  85.             }
  86.             st.insert(x);
  87.         }
  88.     }
  89.  
  90.     for (int i = 0; i < n; i++) {
  91.         vector<int> ret = factorization(a[i] + 1);
  92.         for (int x : ret) {
  93.             if (!st.empty() and st.find(x) != st.end()) {
  94.                 cout << 1 << endl;
  95.                 return;
  96.             }
  97.         }
  98.     }
  99.  
  100.     cout << 2 << endl;
  101. }
  102.  
  103. int tc = 1;
  104.  
  105. int32_t main()
  106. {   
  107.     sieve();
  108.  
  109.     optimize();
  110.     // file(); 
  111.     if(tc){int t;cin>>t;for(int i=1;i<=t;i++)solve(i);} 
  112.     else solve(1);
  113.     return 0;
  114. }
Success #stdin #stdout 0.01s 5324KB
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/3F1M7R
language:
C++14 (gcc 8.3)
created:
11 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!