题意

　　给你一个正整数 \(n\)，求有多少字符集为 \(1\) 到 \(k\) 之间整数的字符串，使得该字符串可以由一个长度为 \(n\) 的回文串循环移位得到。
　　ARC原题 \(100\%\) 的数据是 \(n,k\le 10^9\)
　　SDOI改编后，\(30\%\) 的数据是 \(n,k\le 10^{10}\)，\(60\%\) 的数据是 \(n,k\le 10^{14}\)，\(100\%\) 的数据是 \(n,k\le 10^{18}\)……

题解

\(n,k\le 10^{10}\)

　　考虑一个回文串，设它的循环节长度为 \(x\)，若 \(x\) 为奇数，则对答案贡献 \(x\)；若为偶数，则对答案贡献 \(\frac{x}{2}\)。
　　我们按 \(x\) 把所有字符串分类，统计每一类的数量。
　　设 \(f(i)\) 表示最小循环节长度为 \(i\) 的回文串数量，\(F(i)\) 表示循环节长度为 \(i\)（即 \(i\) 是最小循环节长度的正整数倍）能得到新回文串的回文串数量。
　　则 \[F(i)=\sum\limits_{d|i} f(i)\] \[ans = \sum\limits_{d|n} f(d)\times \begin{cases} d（d为奇数） \\ \frac{d}{2}（d为偶数） \end{cases}\]
　　\(F(i)\) 显然等于 $