fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define yes cout<<"YES\n"
  3. #define no cout<<"NO\n"
  4. #define int long long
  5. #define ff first
  6. #define ss second
  7. #define pb push_back
  8. #define dd double
  9. #define y1 zildjian
  10.  
  11. using namespace std;
  12.  
  13. const int N = 1e6+10;
  14. const int INF = 1e18;
  15. const int mod = 1e9+7;
  16. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  17.  
  18.  
  19. // int binpow (int a, int n) {
  20. // 	if (n == 0)
  21. // 		return 1;
  22. // 	if (n % 2 == 1)
  23. // 		return (binpow (a, n-1)%mod * a%mod)%mod;
  24. // 	else {
  25. // 		int b = binpow (a, n/2) % mod;
  26. // 		return (b%mod * b%mod)%mod;
  27. // 	}
  28. // }
  29. int gcd(int a, int b) {
  30. 	return!b ? a : gcd(b, a % b);
  31. }
  32. int n;
  33. int a[N];
  34. int dp[N];
  35. map<int,int> m;
  36.  
  37. void solve(){
  38.     cin>>n;
  39.     for(int i = 1;i<=n;i++) cin>>a[i];
  40.     int gc = 0;
  41.     vector<int> pos;
  42.     for(int i = 1;i<=n;i++){
  43.         int new_gc = gcd(gc,a[i]);
  44.         if(new_gc != gc) pos.pb(i);
  45.         gc = new_gc;
  46.     }
  47.     int mx = 0;
  48.     for(auto x:pos){
  49.     	cout<<x<<" ";
  50.         gc = 0;
  51.         int ans = 0;
  52.         for(int i = 1;i<=n;i++){
  53.             if(i == x) continue;
  54.             gc = gcd(gc,a[i]);
  55.             ans+=gc;
  56.         }
  57.         mx = max(mx,ans);
  58.     }
  59.     cout<<endl;
  60.     cout<<mx<<'\n';
  61. }
  62.  
  63. //bbab
  64.  
  65. signed main(){
  66.     // freopen("search.in","r",stdin); 
  67.     // freopen("search.out","w",stdout);
  68.     ios_base::sync_with_stdio(0);
  69.     cin.tie(nullptr);
  70.     // cout.tie(nullptr);
  71.     int t = 1;
  72.     // cin>>t;
  73.     for(int i = 1;i<=t;i++){
  74.         // cout<<"Case "<<i<<": ";
  75.         solve();
  76.     }
  77. }
Success #stdin #stdout 0.01s 5580KB
comments (?)
stdin
copy 
3
18 3 9
stdout
copy 
1 2 
27
https://ideone.com/N43T7s
language:
C++14 (gcc 8.3)
created:
2 hours 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!