#include #include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template vector> vec2d(int n, int m, T v){ return vector>(n, vector(m, v)); } template vector>> vec3d(int n, int m, int k, T v){ return vector>>(n, vector>(m, vector(k, v))); } template void print_vector(vector v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } const ll inf = 1e18; ll f(ll p, ll q){ if(gcd(p, q) != 1) return 0; return (p-1)*(q-1); } const int N = 200000; int cnt[N+5]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int n; cin >> n; vector a(n); for(int i = 0; i < n; i++) { cin >> a[i]; cnt[a[i]]++; } for(int x = 2; x <= N; x++){ int c = 0; for(int i = 1; i*x <= N; i++){ c += cnt[i*x]; } if(c >= 2){ vector v; for(int i = 0; i < n; i++){ if(a[i]%x == 0) v.push_back(i); } cout << 0 << endl; cout << v[0]+1 << ' ' << v[1]+1 << endl; for(int i = 0; i < n-2; i++) cout << 1 << ' ' << 2 << endl; return 0; } } vector odd_indices; for(int i = 0; i < n; i++){ if(a[i]%2 == 1) odd_indices.push_back(i); } if(odd_indices.size() >= 4){ int m = odd_indices.size(); cout << 0 << endl; cout << odd_indices[m-2]+1 << ' ' << odd_indices[m-1]+1 << endl; cout << odd_indices[m-4]+1 << ' ' << odd_indices[m-3]+1 << endl; cout << n-3 << ' ' << n-2 << endl; // n-3個 for(int i = 0; i < n-4; i++) cout << 1 << ' ' << 2 << endl; return 0; } if(n == 4){ // 一つだけ偶数があるはず int m = odd_indices.size(); assert(m == 3); cout << 0 << endl; cout << odd_indices[m-2]+1 << ' ' << odd_indices[m-1]+1 << endl; vector rem; for(int i = 0; i < n; i++){ if(i == odd_indices[m-2] || i == odd_indices[m-1]) continue; rem.push_back(i); } for(int i = 0; i < rem.size(); i++){ if(a[rem[i]]%2 == 0) cout << i+1 << ' ' << 3 << endl; } cout << 1 << ' ' << 2 << endl; return 0; } if(n == 3){ ll ans = 4e18; int exepted = -1; if(chmin(ans, f(a[0], f(a[1], a[2])))) exepted = 0; if(chmin(ans, f(a[1], f(a[2], a[0])))) exepted = 1; if(chmin(ans, f(a[2], f(a[0], a[1])))) exepted = 2; cout << ans << endl; if(exepted == 0) cout << 2 << ' ' << 3 << endl; if(exepted == 1) cout << 3 << ' ' << 1 << endl; if(exepted == 2) cout << 1 << ' ' << 2 << endl; cout << 1 << ' ' << 2 << endl; return 0; } if(n == 2){ cout << f(a[0], a[1]) << endl; cout << 1 << ' ' << 2 << endl; return 0; } }