POJ 3101 大数+gcd
2024-09-04 17:56:44
题目大意:
星星作圆周运动的周期给出,若已连成一条线,下一次所有星星在同一条线上的时间
用分数形式输出
这里我们可以利用追及问题来计算出两个星星之间连成一条直线的时间,也即速度快的星星追上速度慢的星星弧度PI
t = PI /abs (2PI / t1 - 2PI / t2) = t1 * t2 / (2 * abs(t1 - t2))
这样前面作为分子后面作为分母,每次得到一个分数记得利用gcd化简
然后把所有两两得到的时间差求个最小公倍数
分数的最大公倍数是分子求最小公倍数, 分母求最大公约数
import java.util.*;
import java.math.*; public class Main { public static void main(String [] args){
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
Integer n;
n = cin.nextInt();
int [] t = new int[1005];
for(int i = 0 ; i<n ; i++)
t[i] = cin.nextInt(); long [] a = new long[1005];
long [] b = new long[1005];
for(int i = 0 ; i<n-1 ; i++){
int tmp1 = t[i] * t[i+1];
int tmp2 = 2 * Math.abs(t[i] - t[i+1]);
int k = GCD(tmp1 , tmp2);
a[i] = tmp1 / k;
b[i] = tmp2 / k;
} BigInteger ans1 = BigInteger.valueOf(a[0]);
BigInteger ans2 = BigInteger.valueOf(b[0]);
for(int i = 1 ; i<n-1 ; i++){
BigInteger tmp = ans1.gcd(BigInteger.valueOf(a[i]));
ans1 = ans1.multiply(BigInteger.valueOf(a[i]));
ans1 = ans1.divide(tmp);
ans2 = ans2.gcd(BigInteger.valueOf(b[i]));
} System.out.println(ans1 + " " + ans2);
}
} public static int GCD(int a , int b){
if(b == 0) return a;
return GCD(b , a%b);
}
}
最新文章
- Android Automotive开发之一《环境: JDK7&;JDK8切换 》
- iOS tableview自定义cell上添加按钮实现删除功能
- 奇葩问题之ToolBar返回键失效
- 点击Cell中的按钮时,如何取所在的Cell
- Daily Scrum5
- [SQL Server系] -- 约束
- springmvc(六)——视图和视图解析器
- android93 进程优先级补充
- poj 2926 Requirements
- hdu 1142 A Walk Through the Forest
- jQuery UI的基本使用方法与技巧
- C# 添加服务引用。
- ARM
- 每周.NET前沿技术文章摘要(2017-05-24)
- 客户端一致性与多Leader机制------《Designing Data-Intensive Applications》读书笔记7
- Python包和版本管理的最好工具----pipenv
- 1.7分布式工具配置及安装(仅供学习Xshell,VMware)
- Oracle查看表空间
- 很好的git教程
- 【BZOJ2427】【HAOI2010】软件安装
热门文章
- chrome 跨域设置-(完善博客内容)
- vue中子组件向父组件传值
- P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm(Tarjan+记忆化)
- Android 性能优化(20)多核cpu入门:SMP Primer for Android
- 几个不同的tab切换示例
- 微信JSSDK支付
- [ CodeForces 1063 A ] Oh Those Palindromes
- Spring注解的步骤
- canvas一周一练 -- canvas绘制饼图(3)
- sql的for update