Question

problema #2619 sau five de pe pbinfo

Se consideră un șir de numere naturale a[1], a[2], …, a[n].


Cerința

Să se determine numărul tripletelor (a[i], a[j], a[p]) cu i < j < p, iar a[i] + a[j] + a[p] este divizibil cu 5.


Date de intrare

Programul citește de la tastatură numerele n, w, X, Y, Z. Șirul de n numere se generează după relațiile: a[1] = w, a[i] = (X * a[i-1] + Y) % Z;


Date de ieșire

Programul va afișa pe ecran numărul tripletelor cu suma divizibilă cu 5.


Restricții și precizări

1 ≤ n ≤ 100 000

1 ≤ w, X, Y, Z ≤ 1 000 000 000


Exemplu

Intrare


10 1 7 223 17

Ieșire


24

problema #2619 sau five de pe pbinfo

Answer 1

#include <iostream>

using namespace std;

int main()

{

   unsigned long long T[100003];

   unsigned long long A[10];

   unsigned long long e=false;

   unsigned long long n,w,X,Y,Z,i,j,r=0,a,d,p;

   for(i=0;i<=4;i++)

   {

       A[i]=0;

   }

   cin>>n;

   cin>>w;

   cin>>X>>Y>>Z;

   T[1]=w;

   A[w%5]++;

   for(i=2;i<=n;i++)

   {

       T[i]=(X*T[i-1]+Y)%Z;

       d=T[i]%5;

       A[d]++;

   }

   r= A[0]*(A[0]-1)*(A[0]-2)/6;

   r+=A[0]*A[1]*A[4];

   r+=A[0]*A[2]*A[3];

   r+=A[3]*(A[1]*(A[1]-1))/2;

   r+=A[1]*(A[2]*(A[2]-1))/2;

   r+=A[4]*(A[4]-1)*A[2]/2;

   r+=A[3]*(A[3]-1)*A[4]/2;

   cout<<r;

   return 0;

}