ProtyayMnd50 / variantsCount.cpp

#include <bits/stdc++.h> using namespace std; #define ll long long long variantsCount(int n, long long s0, long long k, long long b, long long m, long long a) { // Generate all n side lengths vector<long long> sides(n); sides[0] = s0; for (int i = 1; i < n; i++) { sides[i] = ((k * sides[i - 1] + b) % m) + 1 + sides[i - 1]; } // Sort sides for binary search sort(sides.begin(), sides.end()); int count = 0; // Use binary search to count pairs for (int i = 0; i < n; i++) { long long max_side = a / sides[i]; // Find the position where sides[j] exceeds max_side auto j = upper_bound(sides.begin(), sides.end(), max_side) - sides.begin(); count += j; // All elements in sides[0:j] are valid for sides[i] * sides[j] <= a } return count; } int main() { int n = 5; long long s0 = 3, k = 2, b = 1, m = 100, a = 100; int result = variantsCount(n, s0, k, b, m, a); cout << result << endl; return 0; }