让周期时间d[i]从小到大排序，周期时间相同的合并成一个点，最后还剩N个两两周期不同的行星。

那么相邻两个行星的产生半圈的距离差所需时间为T[i] =  d[i]*d[i+1] / (d[i+1]-d[i])*2; 
这样就可以产生N-1个T[i],求出这个N-1个T[i-1]的最小公倍数。 

就这样是在想不出那里有错，谁能指出来思路哪里错了。
我的代码：
#include <iostream>
#include <algorithm>
using namespace std;

 struct Data
 {
	 int numerator ,denominator ;
 };
int d[1001],n,N;
int T[1001];
Data dp[1001];

int gcd(int a, int b)
{
	int tmp;
    if(a<b)
	{
		tmp = a;
		a= b;
		b= tmp;
	}
	while(true){
		if(a%b ==0)
			break;
		tmp =a%b;
		a = b;
		b = tmp;
	}
	return b;
}
int mul(int a, int b)
{
	int g = gcd(a,b);
	b = b/g;
	return a*b;
}
void Mylest(int n1, int d1, int n2, int d2, int &rstN, int &rstD)
{
   rstN  = mul(n1,n2);
   rstD  = gcd(d1,d2);
}
void work(int i)
{
  
   dp[i].numerator = T[i]*T[i+1];
   dp[i].denominator = (T[i+1]-T[i])*2;

   int g  = gcd(dp[i].denominator,dp[i].numerator);

   dp[i].numerator = dp[i].numerator/g;
   dp[i].denominator=dp[i].denominator/g;

}
int main()
{
 //freopen("C:\\ACMData.txt","r",stdin);

	scanf("%d",&n);
	int i=0;
	while(i<n){
		scanf("%d",&d[i]);
		i++;
	}
	sort(d,d+n);
    
    N=0; i=0;
	T[N] = d[i]; i++;N++;
	while( i<n){
       if( d[i] == d[i-1]){
		   i++; continue;
	   }
       else{
		   T[N] = d[i];
		   N++; i++;
	   }
	}
    i=0; 
	while(i<N-1){
	   work(i);
	   i++;
	}  //算法应该没错，难道是哪里没想到！！！！

     int numerator =  dp[0].numerator;
	 int denominator = dp[0].denominator;
	 i=1;  //N个有效点  那么就只有N-1个相邻“最小半圈时间差”
	 while(i<N-1)  //&Ccedil;ó×&icirc;&ETH;&iexcl;&sup1;&laquo;±&para;&Ecirc;&yacute;
	 {
		 Mylest(numerator,denominator,dp[i].numerator,dp[i].denominator,numerator,denominator);
         i++;
	 }

	 int g= gcd(numerator,denominator);
	 numerator = numerator/g;
     denominator=denominator/g;

	 printf("%d %d\n",numerator,denominator);
	 return 0;
}

• 传说要用大整数 (2036) Sempr 2006-11-23 00:46:35
  • Re:传说要用大整数 (10) bmexue 2006-11-23 01:02:48