HackerRank Number Theory – Scalar Products

Challenge: Scalar Products

Subdomeniu: Number Theory (number-theory)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464762752

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/scalar-products/problem

Cerinta

Integer sequence $a$ having length $2n+2$ is defined as follows:

* $a_0 = 0$
* $a_1 = C$
* $a_{i + 2} = (a_{i + 1} + a_i) \ \% \ M$, where $0 \leq i \lt 2n $

Write a function generator, $gen$, to generate the remaining values for $a_2$ through $a_{2n+1}$. The values returned by $gen$ describe two-dimensional vectors $v_1 \dots v_n$, where each sequential pair of values describes the respective $x$ and $y$ coordinates for some vector $v$ in the form $x_1, y_1, x_2, y_2, \ldots, x_n, y_n$. In other words, $v_1 = (a_2, a_3), v_2 = (a_4, a_5), \dots , v_n = (a_{2n}, a_{2n+1})$.

Let $S$ be the set of scalar products of $v_i$ and $v_j$ for each $1 \le i, j \le n$, where $i \neq j$.
Determine the number of different [residues](http://mathworld.wolfram.com/Residue.html) in $S$ and print the resulting value modulo $M$.

Input Format

A single line of three space-separated positive integers: $C$ (the value of $a_1$), $M$ (the modulus), and $n$ (the number of two-dimensional vectors), respectively.

**Constraints**

- $1 \le C \le 10^9$
- $1 \le M \le 10^9$ 
- $1 \le n \le 3 \times 10^5$

Output Format

Print a single integer denoting the number of different residues $\% \ M$ in $S$.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long C, M;
    int n;
    if (!(cin >> C >> M >> n)) return 0;

    if (n <= 1) {
        cout << 0 << '\n';
        return 0;
    }

    int maxIdx = 4 * n - 1;
    vector<long long> F(maxIdx + 1, 0);
    F[0] = 0 % M;
    if (maxIdx >= 1) F[1] = 1 % M;
    for (int i = 2; i <= maxIdx; ++i) {
        F[i] = F[i - 1] + F[i - 2];
        if (F[i] >= M) F[i] -= M;
    }

    long long d = (__int128)(C % M) * (C % M) % M;

    unordered_set<long long> seen;
    seen.reserve((size_t)2 * n + 16);

    for (int t = 3; t <= 2 * n - 1; ++t) {
        int k = 2 * t + 1; // 7,9,...,4n-1
        long long v = (__int128)d * F[k] % M;
        seen.insert(v);
    }

    cout << seen.size() % M << '\n';
    return 0;
}