本文主要是介绍POJ3101 Astronomy【素因子分解】【大数乘法】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://poj.org/problem?id=3101
题目大意：
有 N 个行星绕着中心天体飞行，给你每个行星飞行的周期，问：最少运行多少时间
能让所有的行星在同一条直线上。结果用分数表示。输出该分数的分子和分母。
解题思路：
选择第一个行星为参考系，其周期为 T0，则其他行星的周期为 Ti，则其他行星的相
对角速度为 Vi = (T0-Ti) * 2π / (T0*Ti)。绕过半个圆周的时间 ti = π / Vi =
(T0*Ti) / ((T0-Ti)*2)。
那么问题就变为了求所有 ti 的分子的最小公倍数 和 分子的最大公约数。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN = 1010;int GCD(int a,int b)
{if(b == 0)return a;return GCD(b,a%b);
}int A[MAXN],B[MAXN],C[MAXN*10];int main()
{int N;while(~scanf("%d",&N)){for(int i = 0; i < N; ++i)scanf("%d",&A[i]);memset(B,0,sizeof(B));memset(C,0,sizeof(C));B[0] = 1;int a,b,gcd,fm = 0,k;for(int i = 1; i < N; ++i){if(A[i] != A[0]){b = A[i]*A[0];a = abs(A[i]-A[0])*2;gcd = GCD(a,b);a /= gcd;b /= gcd;fm = GCD(a,fm);for(int j = 2; b > 1; ++j){if(b % j == 0){k = 0;while(b % j == 0){b /= j;k++;}if(k > C[j]) //C[] 数组记录素因子的幂 对应的最大值C[j] = k;}}}}int tmp;for(int i = 0; i < MAXN*10; ++i){for(int j = 0; j < C[i]; ++j){tmp = 0;for(int k = 0; k < MAXN; ++k){B[k] = B[k]*i + tmp;tmp = B[k] / 10000;B[k] %= 10000;}}}int i = 999;while(i > 0 && B[i] == 0)i--;printf("%d",B[i]);for(--i; i >= 0; --i)printf("%04d",B[i]);printf(" %d\n",fm);}return 0;
}
这篇关于POJ3101 Astronomy【素因子分解】【大数乘法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
