首页 > 代码库 > hdu 4919 Exclusive or
hdu 4919 Exclusive or
Exclusive or
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 327 Accepted Submission(s): 137
Problem Description
Given n, find the value of
Note: ⊕ denotes bitwise exclusive-or.
Note: ⊕ denotes bitwise exclusive-or.
Input
The input consists of several tests. For each tests:
A single integer n (2≤n<10500).
A single integer n (2≤n<10500).
Output
For each tests:
A single integer, the value of the sum.
A single integer, the value of the sum.
Sample Input
3 4
Sample Output
6 4
Author
Xiaoxu Guo (ftiasch)
Source
2014 Multi-University Training Contest 5
题解:
下面是官方给的答案:
鉴于比较难以理解官方大神的讲解,这里我研究了一下,下面给出求解化简过程:
图片有些不清晰,凑合看吧 T^T
代码:
import java.util.*; import java.io.*; import java.math.*; public class Main { public static BigInteger zero=BigInteger.valueOf(0); public static BigInteger one=BigInteger.valueOf(1); public static BigInteger two=BigInteger.valueOf(2); public static BigInteger four=BigInteger.valueOf(4); public static BigInteger six=BigInteger.valueOf(6); public static HashMap<BigInteger,BigInteger> map=new HashMap<BigInteger,BigInteger>(); public static BigInteger solve(BigInteger n) { if(map.containsKey(n)) return map.get(n); BigInteger t=BigInteger.valueOf(0); BigInteger k=n.divide(two); BigInteger r=n.mod(two); if(r.compareTo(one)==0) t=solve(k).multiply(four).add(k.multiply(six)); else { t=two.multiply(solve(k)); t=t.add(two.multiply(solve(k.subtract(one)))); t=t.add(four.multiply(k)); t=t.subtract(four); } map.put(n, t); return t; } public static void main(String []args) { BigInteger n; map.put(zero, zero); map.put(one,zero); Scanner cin = new Scanner(System.in); while(cin.hasNext()) { n=cin.nextBigInteger(); System.out.println(solve(n)); } } } /* 借鉴别人的代码,学习了一下java大数和HashMap的用法,可以当作模版来使用了。 *转载请注明出处,谢谢。 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。