fork download
copy 
  1. // divisible subarray using pigeon hole 
  2. #include<iostream>
  3. #include<math.h>
  4. #include<cstring>
  5. #define ll long long
  6. #define size 100000
  7. #define f(i,j,n) for(i=j;i<n;i++) 
  8. #define MOD 1000000007
  9.  
  10. using namespace std;
  11.  
  12. int main(){
  13.     int t,n;
  14.     cin>>t;
  15.     while(t--){
  16.         cin>>n;
  17.         int a[n],p[n+1],dup[n]={0};
  18.         p[0]=0;
  19.         dup[0]=1;
  20.         for(int i=0;i<n;i++){
  21.             cin>>a[i];
  22.             p[i+1]=(p[i]+a[i]%n)%n;//taking subarray sum%n;
  23.             dup[p[i+1]]++;
  24.         }
  25.         //subarray created
  26.         // now find all the no.s and take two out of all present duplicates in p[]
  27.         int ans=0,c;
  28.         for(int i=0;i<n;i++){
  29.             c=dup[i];
  30.             if((c>=2)){
  31.                 ans+=(c*(c-1)/2);
  32.             }
  33.         }
  34.         cout<<ans<<endl;
  35.  
  36.     }
  37.     return 0;
  38. }
Runtime error #stdin #stdout 0s 4128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tqygyn
language:
C++ (gcc 8.3)
created:
7 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!