UOJ Logo LFYZ Online Judge

LFYZOJ

#354. 【2015 北京区域赛 K】数学题(A Math Problem)

统计

原题链接

问题描述

函数 $f(x)$ 适合:

$$\begin{aligned}&f(1)=1,\\&3f(n)f(2n + 1) = f(2n)(1 + 3f(n)),\\&f(2n) \lt 6f(n)\end{aligned}$$

函数 $g(t), t \in [0..k - 1]$ 是区间 $[1..n]$ 内使 $f(i) \% k = t$ 之 $i$ 之数量,求 $g(t)$ 之异或和。

输入输出

输入一行两整数 $n, k$,输出一行一整数代表上述结果。

样例一

Input

5 5

Output

3

数据范围

数据原创。所有数据:$$n \le 10^{18}, k \in \{3, 5, 17, 257, 65537\}$$

时限 1s,空限 256MB