有个恒星系，有n个行星，其中第i个以时间t_i为周期绕恒星做圆周运动，问行星们在过恒星的同一条直线上的时刻之间的间隔。 N<=1000,t_i<=10000
首先要注意到行星可以在圆的两边。 然后所有行星都过同一条直线可以看成任取i，i和i+1在同一直线上。 那么通过一波计算，可以得出i和i+1的时间间隔，是一个分数，记为ai/bi。 接着我们要做的就是把所有分数弄一个最小公倍数就好了，即分别乘上某个整数，使得所有分数相等。 猜结论，答案为lcm(ai)/gcd(bi)。只需要证明，答案除以了某个ai/bi后，为整数，任取i，除出来的整数都互质即可。 注意t有可能相同，还有数据范围。
没打高精度，懒得打了····
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef double db; typedef long long ll; #define fo(i,j,k) for(i=j;i<=k;i++) #define fd(i,j,k) for(i=j;i>=k;i--) const int N=10005; ll a[N],b[N],c[N],t[N],lc,gc,i,n,m; ll gcd(ll a,ll b) { if (!b) return a; return gcd(b,a%b); } int main() { scanf("%lld",&n); fo(i,1,n) scanf("%lld",c+i); sort(c+1,c+1+n); fo(i,1,n-1) if (c[i]!=c[i+1]) t[++m]=c[i]; n=m; fo(i,1,n-1) { a[i]=t[i]*t[i+1]; b[i]=2*abs(t[i+1]-t[i]); gc=gcd(a[i],b[i]); a[i]/=gc; b[i]/=gc; } lc=a[1]; gc=b[1]; fo(i,2,n-1) { lc=lc*a[i]/gcd(lc,a[i]); gc=gcd(gc,b[i]); int kx=gcd(lc,gc); lc/=kx; gc/=kx; } printf("%lld %lld",lc,gc); }