Yet Another Problem About Sequences
For a set of positive integers S, let's define gcd(S) as the greatest integer which divides each element of S. If gcd(S)=1, the set S is called coprime. For example, the set {7,12,15} is coprime, but {6,12,15} is not coprime, since every element of this set is divisible by 3.
Your task is to find an integer sequence A0,A1,…,AN−1 such that:
for each valid i, 1≤Ai≤109
A0,A1,…,AN−1 are pairwise distinct
for each valid i, the set {Ai,A(i+1)%N} is not coprime (% denotes the modulo operator)
for each valid i, the set {Ai,A(i+1)%N,A(i+2)%N} is coprime
It is possible that there is no solution. If there are multiple solutions, you may find any one.
Example Input
2
3
4
Example Output
6 10 15
374 595 1365 858
Explanation
Example case 1: Let's check the answer: gcd(6,10)=2, gcd(10,15)=5, gcd(15,6)=3, gcd(6,10,15)=1. Every two cyclically consecutive numbers are not coprime, but every three cyclically consecutive numbers are coprime.
Example case 2:
gcd(374,595)=17, gcd(595,1365)=35, gcd(1365,868)=39, gcd(858,374)=22
gcd(374,595,1365)=1, gcd(595,1365,858)=1, gcd(1365,858,374)=1, gcd(858,374,595)=1
Problem link : https://www.codechef.com/JAN19A/problems/EARTSEQ/
Your task is to find an integer sequence A0,A1,…,AN−1 such that:
for each valid i, 1≤Ai≤109
A0,A1,…,AN−1 are pairwise distinct
for each valid i, the set {Ai,A(i+1)%N} is not coprime (% denotes the modulo operator)
for each valid i, the set {Ai,A(i+1)%N,A(i+2)%N} is coprime
It is possible that there is no solution. If there are multiple solutions, you may find any one.
Example Input
2
3
4
Example Output
6 10 15
374 595 1365 858
Explanation
Example case 1: Let's check the answer: gcd(6,10)=2, gcd(10,15)=5, gcd(15,6)=3, gcd(6,10,15)=1. Every two cyclically consecutive numbers are not coprime, but every three cyclically consecutive numbers are coprime.
Example case 2:
gcd(374,595)=17, gcd(595,1365)=35, gcd(1365,868)=39, gcd(858,374)=22
gcd(374,595,1365)=1, gcd(595,1365,858)=1, gcd(1365,858,374)=1, gcd(858,374,595)=1
Problem link : https://www.codechef.com/JAN19A/problems/EARTSEQ/
n=3 6,10,15
n=4 6,21,35,40
n=5 10,22,33,39,65
n=6 6,33,55,65,91,98
is there any pattern here ?
n=4 6,21,35,40
n=5 10,22,33,39,65
n=6 6,33,55,65,91,98
is there any pattern here ?
Consider the prime factors of your n=6 example:
browni3141 is right. These problems are boring!
2 3 5 7 11 13 6: 1 1 33: 1 1 55: 1 1 65: 1 1 91: 1 1 98: 1 2 |
browni3141 is right. These problems are boring!
@dutch
the pattern in the above fig you showed will only get an user partial points
because if your algorithm is based on the observations from above figure,
your answer will not be fulfilling the first constraint , i.e. 1≤Ai≤10**9.
the pattern in the above fig you showed will only get an user partial points
because if your algorithm is based on the observations from above figure,
your answer will not be fulfilling the first constraint , i.e. 1≤Ai≤10**9.
@dutch maxdaen is right. It will not work. Maximum value of a[i] will reach upto ^10**12/13 which will break the constraint.
Topic archived. No new replies allowed.