Soluție HackerRank pentru The Chosen One, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: The Chosen One
- Domeniu: Number Theory
- Limbaj: C++14
Challenge: The Chosen One
Subdomeniu: Number Theory (number-theory)
Scor cont: 40.0 / 40
Submission status: Accepted
Submission score: 1.0
Submission ID: 464736855
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/the-chosen-one/problem
Cerință
You are given a sequence of n integers, a_0, a_1, …, a_n-1. Find and print any integer x such that x is divisor of every a_i except for exactly one element.
Input Format
The first line contains an integer, n, denoting the length of the sequence.
The second line contains n positive space-separated integers describing a_0, a_1, …, a_n-1.
Output Format
Print any positive integer denoting x such that x is a divisor of exactly n-1 of the sequence's elements. x must be between 1 and 2 · 10^18
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ a_i ≤ 10^18
- It is guaranteed that a solution exists.
Cod sursă
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long getDivisor(long long a[], long long n) {
if (n == 1)
return (a[0] + 1);
long long prefix[n], suffix[n];
prefix[0] = a[0];
for (long long i = 1; i < n; i++)
prefix[i] = __gcd(a[i], prefix[i - 1]);
suffix[n-1] = a[n-1];
for (long long i = n - 2; i >= 0; i--)
suffix[i] = __gcd(suffix[i + 1], a[i]);
for (long long i = 0; i <= n; i++) {
long long t = 0;
if (i == 0)
t = suffix[i + 1];
else if (i == n - 1)
t = prefix[i - 1];
else
t = __gcd(prefix[i - 1], suffix[i + 1]);
if (a[i] % t != 0)
return t;
}
return 0LL;
}
int main(){
long long n = 1;
cin >> n;
long long a[n];
for(long long i=0;i<n;i++) cin >> a[i];
cout << getDivisor(a,n) << '\n';
return 0;
}