晚上,室友给了我到题目,说是让我用Java的大数实现以下。正好也熟悉一下java BigInteger,比赛的时候正好可以用得到。
题目:
Positive Negative Sign
小胖子koko最近重温幼儿园数学,问题是这样子滴,给你两个整数n和m,保证n可以被2m整除,你要把前n个自然数写在纸上,先将前m个整数的符号置为负号,然后将接下来的m个整数的符号置为正,然后将接下来的m个整数符号置为负,循环。。知道n个整数都已经被加上符号位
例如:n=12,m=3时
-1 -2 -3 +4 +5 +6 -7 -8 -9 +10 +11 +12
这也太简单了吧!可是koko还是不会呢。。。没办法。。他只好来请教炒鸡聪明的你啦
你的任务是编写一个程序帮小胖子koko求出这些被加上了正负号数字的和
Input
输入以T开始,代表测试样例的个数(T<=1000)
每组样例包括两个整数:n(n<10^1000)和m,测试数据保证n总是可以被2×m整除
Output
对于每组测试数据,输出样例号和答案,格式参见样例输出
Sample Input Output for Sample Input
2
12 3
4 1 Case 1: 18
Case 2: 2
思路:刚开始的时候我直接模拟做得,后来他跟我说这个题要是模拟做得话肯定超时了,然后有告诉了我思路,其实这个题很简单的:只考虑前2^m个数就行,第i个数和第(i+m)个数配对,结果就是m,所以最终的结果就是n*m/2。但是这个题的数据范围很大,用java的大数处理起来就很方便啊。
代码:
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int T = cin.nextInt();
int cnt = 0;
for (int i=0; i<T; i++)
{
BigInteger num = cin.nextBigInteger();
BigInteger m = cin.nextBigInteger();
BigInteger ans =new BigInteger("0");
BigInteger a = new BigInteger("2");
ans = num.multiply(m);
ans = ans.divide(a);
cnt++;
System.out.print("Case"+" "+cnt+":");
System.out.println(ans);
}
}
}
通过这个题,把Java的BigInteger学习一下,下面给个链接吧:
http://www.cis.upenn.edu/~bcpierce/courses/629/jdkdocs/api/java.math.BigInteger.html
写的挺详细的。