> 让周期时间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)  //Çó×îС¹«±¶Êý
> 	 {
> 		 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;
> }

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