Блог пользователя otero1991

Автор otero1991, 14 лет назад, По-английски

After removing some elements from a geometric sequence (with not necessary integer ratio), I wonder how can I recover this ratio, and if there are some possibles ratios the one with the greatest absolute value. The solution should be linear or nlogn. The numbers are not greater than 10^18

This problem is from the contest Waterloo Local Contest 24 September (Gym)

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Hint 1: the ratio must always be rational and greater than one by absolute value.
Hint 2: we can have a long geometric series if and only if the ratio is 1 or -1.

»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone has another idea???

»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

I think there is something wrong with this problem. because we know that every geometric sequence is donated by two numbers r and a0, where r is the ratio and a0 is the first element of the sequence.

because the input is a geometric sequence after removing some elements. we don't have any way to know what is the first element.

but I will tell you a way to tell the ratio of the geometric sequence assuming that the ratio is guaranteed bigger than 1 and it is exist.

let the elements of the geometric sequence be: a0 , a0*r , a0*r^2 , a0*r^3 , .... , a0*r^k

now after removing some elements the array will become:

a0*r^i , a0*r^j , a0*r^k , a0*r^l , a0*r^m ..... where i < j < k < l < m (assume the number of remaining elements is N)

Let's divide each two adjacent numbers in the array so we get rid of the a0's in the elements so we will have:

r^(j-i) , r^(k-j) , r^(l-k) , r^(m-l) notice the number of elements of the new array is N-1)

now just compute the GCD of the powers of the elements of the new array and you will get the greatest possible ratio of the geometric sequence.

for example the solution is: r^GCD(j-i,k-j,l-k,m-l)

»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

This is the solution, it works only if it's guaranteed that ratio is integer ,ratio is exist ,the ratio bigger than 1 and 3<=N<=100,000:

#include <iostream>
using namespace std;
int arr[100005];
int n;
int sol;
int GCD_of_power(int a,int b){
	int t,y;
	if(a>b){
		t=a;
		y=b;
	} else {
		t=b;
		y=a;
	}
	if(y==1){
		return t;
	}
	return GCD_of_power(y,t/y);
}
int main(){
	int a,b;
	cin>>n;
	cin>>a;
	for(int i=0;i<n-1;i++){
		cin>>b;
		arr[i]=b/a;
		a=b;
	}
	sol=GCD_of_power(arr[0],arr[1]);
	for(int i=2;i<n-1;i++){
		sol=GCD_of_power(sol,arr[i]);
	}
	cout<<sol<<endl;
}