280
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
#include <bits/stdc++.h> using namespace std; long long a[20]; long long Comb(long long n, long long k) { if (n < k)return 0; long long rez = 1; for (long long i = n - k + 1; i <= n; i ++) rez *= i; for (long long i = 1; i <= k; i ++) rez /= i; return rez; } int main() { long long n, w, x, y, z, rez = 0; cin >> n >> w >> x >> y >> z; a[w % 5] ++; for (int i = 2; i <= n; i ++) { w = (w *x + y) % z; a[w % 5] ++; } for (int i = 0; i < 5; i ++) for (int j = i; j < 5; j ++) { if (i == 0 && j == 0) rez += Comb(a[0], 3); else { int k = (5 - (i + j) % 5) % 5; if (k >= j) { if (i == j)rez += Comb(a[j], 2) * a[k]; else if (j == k)rez += Comb(a[j], 2) * a[i]; else rez += a[i] * a[j] * a[k]; } } } cout << rez; return 0; }
Comentarii