acm随笔

算法

遇到异或，总归关于数学，先将有关于异或的式子以及性质全部列出来，根据题目选取有用的

  • a+b=（a^b）+ 2 * （a&b）

  • (a&b）&（a^b）= 0

  • a^a=0

  • x=a^a^x

  • a^0=a

  • 一个序列异或起来等于0，将序列分成两个集合，不管怎么分，两个集合内部异或起来得到的结果肯定相等

  • 一个序列的异或和一定小于等于数值和（异或的本质是二进制下的不进位加法，相比起进位的普通加法，所得的结果当然会较小）==>a^b<=a+b

  • a^b>=a-b

  • 一个序列的数值和 和 异或和 奇偶性相同

  • 如果a^b已知=x或者a&b已知=y，那么要确定a和b，只要进行分配1即可

然后如果都没用到的话，大概是单独考虑每一位

x%p=y,则x=kp+y
^为异或
所以g^(p-1)=kp+1
g=(k*p+1)^(p-1)