Soluție HackerRank pentru Scalar Products, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Scalar Products
- Domeniu: Number Theory
- Limbaj: C++14
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
Cerință
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 ≤ 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 … 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, …, x_n, y_n. In other words, v_1 = (a_2, a_3), v_2 = (a_4, a_5), … , v_n = (a_2n, a_2n+1).
Let S be the set of scalar products of v_i and v_j for each 1 ≤ i, j ≤ n, where i ≠ 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 ≤ C ≤ 10^9
- 1 ≤ M ≤ 10^9
- 1 ≤ n ≤ 3 × 10^5
Output Format
Print a single integer denoting the number of different residues % M in S.
Cod sursă
#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;
}