冬训第三天。我发现参加寒假集训contest的同学是一天比一天少。
今天练习java，四道题其实只有Problem B值得一说，而且我还是在『亮亮』学长的思路指点下才写出来的代码。效果倒是真的很不错。
http://acm.hit.edu.cn/hoj/contest/view?id=100129
Problem A：Hello Java
给出A、B、P求 A * B % P，唯一一点就是三者全都0< <=2^63-1。目测C++的longlong会溢出，经我的实地检验果然溢出
（╮(╯_╰)╭|||使用“分配律”((A % P) * (B % P)) % P 也是不行哒）。用java的biginteger一击制敌。
/*This Code is Submitted by acehypocrisy for Problem 4000090 at 2012-01-20 09:21:44*/
import java.util.*;
import java.math.*;
public class Main {
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
while (cin.hasNextBigInteger()){
BigInteger A = cin.nextBigInteger();
BigInteger B = cin.nextBigInteger();
BigInteger P = cin.nextBigInteger();
System.out.println(A.multiply(B).mod(P));
}
}
}
Problem B：Ugly Numbers
寻找丑数，这道题比原题简单，只要输出第1500个即可，所以可以选择本地跑出结果后print上去。在1s之内出结果也是没问题的。下面的代码的思路是亮神指点的，我等蒟蒻受益匪浅……
首先要明确一点的是，因为丑数的因数只有2 3 5三个数，所以说所有丑数（除1外）都是是可以根据之前的丑数推出来的。
存三个数组索引，把他想成三组一样的数据也不为过。一组数据只负责*2，一组只负责*3，一组只负责*5。这样从1开始就可以推出所有的丑数了。首先要保证当前这三个索引所存的数据分别*2、*3、*5之后比目前最大的丑数还要大。然后比较他们*2、*3、*5之后的数据，选择小的那个作为新的丑数，并且对索引进行一些处理以满足上面说的那一条“保证”。然后就是循环了，循环到1500即可。
本地测试0.016s给出结果，oj评测0.00s。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Index{
int temp;
int index;
int step;
}myindex[3];
bool compare(const Index& A, const Index& B){
if (A.temp < B.temp)
return true;
else
return false;
}
int ugly_number[1500];
int main()
{
myindex[0].index = myindex[1].index = myindex[2].index = 0;
myindex[0].step = 2;
myindex[1].step = 3;
myindex[2].step = 5;
int n = 1;
ugly_number[0] = 1;
while (n < 1500){
myindex[0].temp = ugly_number[myindex[0].index] * myindex[0].step;
myindex[1].temp = ugly_number[myindex[1].index] * myindex[1].step;
myindex[2].temp = ugly_number[myindex[2].index] * myindex[2].step;
sort(&myindex[0], &myindex[3], compare);
for(int i = 0; i < 3; i++){
if (myindex[i].temp > ugly_number[n-1]){
myindex[i].index++;
ugly_number[n] = myindex[i].temp;
n++;
break;
}
}
for(int i = 0; i < 3; i++){
while (ugly_number[myindex[i].index] * myindex[i].step <= ugly_number[n-1])
myindex[i].index++;
}
}
printf("The 1500'th ugly number is %d.\n", ugly_number[1499]);
return 0;
}
另外要提到的是我原来的代码myindex是叫index的，但是交上去编译错误，大意就是和string.h里面的一个函数重名了。。。
哦，在多说一句，代码里面中间的for当时是为了挑出最小的、而且比目前最大丑数大的那个数，不过既然有了下面的while，这句for就显得有点多余了。。
Problem C & D：Fibonacci Sequence
最最基本的斐波那契数列了，其实C和D是一样的，只不过D要求高精度了而已。。所以只贴D的代码了，用java
/*This Code is Submitted by acehypocrisy for Problem 4000094 at 2012-01-20 09:35:58*/
import java.util.*;
import java.math.*;
public class Main {
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
while (cin.hasNextInt()){
int n = cin.nextInt();
BigInteger F1 = BigInteger.valueOf(0);
BigInteger F2 = BigInteger.valueOf(1);
BigInteger F3 = F1.add(F2);
for (int i = 0;i < n - 2; i++){
F1 = F2;
F2 = F3;
F3 = F1.add(F2);
}
if (n == 0)
System.out.println(0);
else if (n == 1)
System.out.println(1);
else
System.out.println(F3);
}
}
}