fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mp make_pair
  4. #define pb push_back
  5. #define lb lower_bound
  6. #define up upper_bound
  7. #define vll vector<ll>
  8. #define G vector<vll >
  9. #define gg vector<int>
  10. #define F first
  11. #define S second
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define RFOR(i,a,b) for(int i=a;i>=b;i--)
  15. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  16. #define endl '\n'
  17. #define clr(a) memset(a,0,sizeof(a))
  18. #define all(x) x.begin(),x.end()
  19. #define rll read_ll();
  20. #define gc getchar
  21. #define pc putchar
  22. typedef long long ll;
  23. template<class T> inline T lcm(T a,T b){
  24.         return a/gcd(a,b)*b;
  25. }
  26. template<typename T>
  27. void debug(T first) {
  28.     cout << first << "\n";
  29. }
  30. template<typename T, typename... Args>
  31. void debug(T first, Args... args) {
  32.     cout << first << " ";
  33.     debug(args...);
  34. }
  35. int inv(int a, int b){
  36.  return 1<a ? b - inv(b%a,a)*b/a : 1;
  37. }
  38.  
  39. ll read_ll(){char c=gc();while((c<'0'||c>'9')&&c!='-')c=gc();ll ret=0;int neg=0;if(c=='-')neg=1,c=gc();while(c>='0'&&c<='9'){ret=10*ret+c-48;c=gc();}return neg?-ret:ret;}
  40.  
  41. void solve()
  42. {
  43.     ll n,m,k,answer = 0;
  44.     n = rll m = rll k = rll
  45.  
  46.     vector<ll>A(n),product(n),zeroes;
  47.     zeroes.pb(-1);
  48.     FOR(i,0,n-1)
  49.     {
  50.         cin>>A[i];
  51.         if(A[i]%m == 0)
  52.             zeroes.pb(i);
  53.         A[i]%=m;
  54.     }
  55.     zeroes.pb(A.size());
  56.     product[0] = A[0];
  57.     FOR(i,1,n-1)
  58.     {
  59.         if(product[i-1] == 0) product[i] = A[i];
  60.         else 
  61.         product[i] = (A[i]*product[i-1])%m;
  62.     }
  63.  
  64.     unordered_map<ll,ll>hash;
  65.     FOR(i,0,n-1)
  66.     {
  67.         if(product[i] == 0)
  68.         {
  69.             hash.clear();
  70.             continue;
  71.         }
  72.         if(product[i] == k)
  73.             answer++;
  74.         if(hash.find(product[i]) != hash.end())
  75.             answer += hash[product[i]];
  76.         auto insert = (product[i]*k)%m;
  77.         if(hash.find(insert) != hash.end())
  78.             hash[insert] += 1;
  79.         else hash.insert({insert,1});
  80.     }
  81.  
  82.     if(k==0)
  83.     {
  84.         for(int j=1;j<zeroes.size()-1;j++)
  85.         {
  86.             answer+= (zeroes[j]+1)*(zeroes[j+1]-zeroes[j]);
  87.         }
  88.     }
  89.  
  90.     cout<<answer<<endl;
  91. }
  92.  
  93. int main()
  94. {
  95.     // cout<<inv(2,3)<<endl;
  96.     int t;cin>>t;
  97.     while(t--)
  98.     {
  99.         solve();
  100.     }
  101.    return 0;
  102. }
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
2
1 11 0
11
5 3 2
2 2 2 2 2
stdout
copy 
1
9
https://ideone.com/bwSQoJ
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!