Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define pb push_back
- #define int long long
- #define uint __int128
- #define mp make_pair
- #define left left_compile
- #define right right_compile
- #pragma GCC optimize("O3")
- #pragma GCC optimize("unroll-loops")
- const int INF = (int)1e18;
- const int md = 998244353;
- const int MAXN = (int)1e5 + 10;
- const int N = (int)2e5 + 111;
- const int debug = 0;
- const long double eps = 1e-7;
- typedef tree<
- int,
- null_type,
- less_equal<int>,
- rb_tree_tag,
- tree_order_statistics_node_update>
- ordered_set;
- int bpow(int a,int b){
- if(b == 0)
- return 1ll;
- if(b % 2 == 0){
- int t = bpow(a,b/2);
- return (t * t) % md;
- }
- return (a * bpow(a,b-1)) % md;
- }
- int inv(int a){ /// return 1/a by PRIME modulo md
- return bpow(a,md-2);
- }
- void myerase(ordered_set& st, int t){
- int r = st.order_of_key(t);
- ordered_set::iterator it = st.find_by_order(r);
- st.erase(it);
- return;
- }
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- void init(){
- return;
- }
- int t[(int)4e5+11];
- int a[(int)2e5+11];
- void build(int v,int l,int r){
- if(l > r)
- return;
- if(l == r){
- t[v] = a[l];
- return;
- }
- int m = (l + r) >> 1;
- build(v<<1,l,m);
- build(v<<1|1,m+1,r);
- t[v] = __gcd(t[v<<1],t[v<<1|1]);
- return;
- }
- int get(int v,int l,int r,int tl,int tr){
- if(l == tl && tr == r)
- return t[v];
- if(l > r || tl > tr)
- return 0;
- int m = (l + r) >> 1;
- return __gcd(get(v<<1,l,m,tl,min(tr,m)),get(v<<1|1,m+1,r,max(tl,m+1),tr));
- }
- void solve_case(){
- int c;
- cin >> c;
- int n;
- cin >> n;
- for(int i = 0; i < n; i++){
- cin >> a[i];
- }
- int g = a[0];
- for(int i = 0; i < n; i++){
- g = __gcd(g,a[i]);
- }
- if(c == 1){
- cout << g * n;
- return;
- }
- int cnt = 0;
- for(int i = 0; i < n; i++){
- a[i] /= g;
- cnt += (a[i] == 1);
- }
- vector<int> ans;
- if(cnt > 0){
- bool upd = true;
- while(upd){
- upd = false;
- for(int i = 0; i + 1 < n; i++){
- if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 && a[i+1] != 1)){
- a[i] = a[i+1] = __gcd(a[i],a[i+1]);
- ans.pb(i+1);
- upd = true;
- }
- }
- }
- upd = true;
- while(upd){
- upd = false;
- for(int i = 0; i + 1 < n; i++){
- if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 || a[i+1] != 1)){
- a[i] = a[i+1] = __gcd(a[i],a[i+1]);
- ans.pb(i+1);
- upd = true;
- }
- }
- }
- cout << ans.size() << "\n";
- for(auto x : ans)
- cout << x << " ";
- return;
- }
- build(1,0,n-1);
- int tl,tr;
- tl = 0, tr = n - 1;
- for(int i = 0; i < n; i++){
- if(get(1,0,n-1,i,n-1) != 1)
- break;
- int l = i + 1, r = n - 1;
- while(l - r > 1){
- int m = (l + r) >> 1;
- if(get(1,0,n-1,i,m) == 1)
- r = m;
- else
- l = m + 1;
- }
- l = (get(1,0,n-1,i,l) == 1 ? l : r);
- if(tr - tl > l - i){
- tr = l, tl = i;
- }
- }
- for(int i = tl; i < tr; i++){
- a[i] = a[i+1] = __gcd(a[i],a[i+1]);
- ans.pb(i+1);
- }
- bool upd = true;
- while(upd){
- upd = false;
- for(int i = 0; i + 1 < n; i++){
- if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 && a[i+1] != 1)){
- a[i] = a[i+1] = __gcd(a[i],a[i+1]);
- ans.pb(i+1);
- upd = true;
- }
- }
- for(int i = 0; i + 1 < n; i++){
- if(__gcd(a[i],a[i+1]) == 1 && a[i] != a[i+1]){
- a[i] = a[i+1] = __gcd(a[i],a[i+1]);
- ans.pb(i+1);
- upd = true;
- }
- }
- }
- cout << ans.size() << "\n";
- for(auto x : ans){
- cout << x << " ";
- }
- return;
- }
- signed main(){
- ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- // freopen("input.txt","r",stdin);
- // freopen("output.txt","w",stdout);
- init();
- int tests = 1;
- // cin >> tests;
- for(int _ = 1; _ <= tests; _++){
- // n = _;
- solve_case();
- }
- return 0;
- }
- /*
- max(a[i],a[i+1],a[i+2]) - min(a[i],a[i+1],a[i+2])
- -2 * a[i] - 2 * a[i+1] - 2 * a[i+2]
- 1
- 9
- 1 2
- 1 3
- 2 4
- 2 5
- 3 6
- 3 7
- 1 8
- 6 9
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement