夜雨寄北

李商隱

君問歸期未有期，巴山夜雨漲秋池。
何當共剪西窗燭，卻話巴山夜雨時。

最近训练时敲代码总爱在 if 语句中有位算符时踩坑， 比如 if(i&1==0) 或 if(i&i-1 == 0)，本意是想判 i 是否为偶数和 i 是否为 2 的幂，但这么写都是错误的，导致程序不能输出正确结果。每次 debug 时又不明所以，耗了很长时间才找到。在这里记录下。

错误的原因是 == 运算符优先级要高于 & | ^ 这三个位运算符，故导致上面代码的判断顺序实际为 if(i & (1==0)) 和 if(i & (i-1 == 0))。 很痛苦呀，有没有。

建议：

• 判断式中如果同时存在位运算符和小于等于大于时，将位运算符表达式加上括号
• 判等时，如果一边是常数一边是变量，将常数放于判等左边。 （TAT，当时听郝斌老师讲这条时还不以为意，心想判等自己肯定不会写成 = , 现在想来，真是内牛满面呀，这条规则实在太好了）

臨江仙 送錢穆父

蘇軾

传送门： 2018 Multi-University Training Contest 2 1007 Naive Operations

题目

Naive Operations

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 502768/502768 K (Java/Others)

Problem Description

In a galaxy far, far away, there are two integer sequence a and b of length n.
b is a static permutation of 1 to n. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for $a_l,a_{l+1}…a_r$
2. query l r: query $\sum_{i=l}^r \lfloor a_i / b_i \rfloor$

求逆序对数有多种方法，如归并排序法、线段树 \ 树状数组法、离散化。

归并排序法几乎就是归并排序。

白书讲解

归并排序思路很简单， 但自己一直不会敲， 也没敲过。 大学算法课本上的代码丑得不行， 嫌弃得要死。 所以自己只知道它的思想。 这几天打高校遇到了求逆序数对的问题，用树状数组来写会爆内存，需要用到归并的思想。于是自己打算好好看一下归并排序，发现紫书上的代码非常简洁，心喜，很快就记住了这段代码，并用自己喜欢的风格敲了一遍。

传送门：https://www.nowcoder.com/acm/contest/141/H

题目描述

Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters another coprime pairs problem, he comes up with diff-prime pairs problem.

传送门：https://www.nowcoder.com/acm/contest/141/A

题目描述

Eddy was a contestant participating in ACM ICPC contests. ACM is short for Algorithm, Coding, Math. Since in the ACM contest, the most important knowledge is about algorithm, followed by coding(implementation ability), then math. However, in the ACM ICPC World Finals 2018, Eddy failed to solve a physics equation, which pushed him away from a potential medal.

当元素较少时，可以使用二进制码来表示集合。集合 ${0， 1， 2， \ldots，n-1}$ 的子集可以用如下方式编码成整数。$$f (S) = \sum_{i \in S} 2^i$$

像这样表示之后，一些集合运算可以对应地写成如下方式。

• 空集 $\phi$——0
• 只含有第 $i$ 个元素的集合 ${i}$——$1<<i$
• 含有全部 $n$ 个元素的集合 ——$(1<<n)-1$
• 判断第 $i$ 个元素是否属于集合 $S$—— if( S>>i&1 ) 或 if(S & (1<<i))
• 向集合 $S$ 加入第 $i$ 个元素 ——S |= 1<<i
• 从集合 $S$ 中去除第 $i$ 个元素 ——S&~(1<<i)
• 集合 $S​$ 和集合 $T​$ 的交集 ——S&T
• 集合 $S$ 和集合 $T$ 的并集 ——S|T
• 切换第 i 位 ——S ^= 1<<i
• 判断某状态是否有相邻的两者相同 ——if( S & S<<1 )
• 把一个数字二进制下最靠右的第一个 1 去掉 ——S = S&(S-1)

此外，想要将集合 {0,1,….,n-1} 所有子集枚举出来的话，可以像下面这样写

1
2
3
4

for(int S=0; S < 1<<n; S++)
{
	//对子集的操作    
}

1001 Maximum Multiple

Problem Description

Given an integer n, Chiaki would like to find three positive integers x, y and z such that: $n=x+y+z$, $x\mid n$, $y \mid n$, $z \mid n$ and $xyz$ is maximum.

Input

There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 10^6$), indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^{6}$).

Output

For each test case, output an integer denoting the maximum $xyz$. If there no such integers, output $-1$ instead.