fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define inf 5e18
  4. #define pb push_back
  5. #define mk make_pair
  6. #define all(x) x.begin(), x.end()
  7. #define rall(x) x.rbegin(),x.rend()
  8. #define sitr set<int>::iterator
  9. #define mitr map<int, int>::iterator
  10. #define pii pair<int, int>
  11. #define vii vector<pii>
  12. #define vi vector<int>
  13. #define vll vector<unsigned int>
  14. using namespace std;
  15.  
  16.  
  17. signed main()
  18. {
  19.     int n,k;
  20.     cin>>n>>k;
  21.     vi a(n);
  22.     int sum = 0;
  23.     for(int i=0;i<n;i++) cin>>a[i], sum += a[i];
  24.     if(sum%k == 0) return cout<<0, 0;
  25.     vi pref(n);
  26.     int num = sum%k;
  27.     pref[0] = a[0]%num;
  28.     if(pref[0] == 0) return cout<<1, 0;
  29.     int mn = inf;
  30.     for(int i=1;i<n;i++) {
  31.         pref[i] = (pref[i-1] + a[i]) % num;
  32.         if(pref[i] == 0) mn = min(mn, i+1);
  33.     }
  34.     map<int,vi> mp;
  35.     for(int i=0;i<n;i++) mp[pref[i]].pb(i);
  36.     for(auto &i : mp) {
  37.         for(int j=0;j<i.second.size()-1;j++) mn = min(mn, i.second[j+1]-i.second[j]);
  38.     }
  39.     cout<<mn;
  40.     return 0;
  41. }
  42.  
  43.  
  44. /*
  45. max factors number = 720720 --> 240 factors
  46. max factors number = 1441440 -->288 factors
  47. Beautiful program
  48. Please run for me.
  49. I've tried you in BASIC,
  50. FORTRAN and C.
  51. Beautiful program,
  52. You've errors galore.
  53. And each time I run you,
  54. You're swapped out of core.
  55. */
Success #stdin #stdout 0s 4576KB
comments (?)
stdin
copy 
4 6
3 1 4 2
stdout
copy 
1
https://ideone.com/wdLtOU
language:
C++14 (gcc 8.3)
created:
5 years 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!