{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css\" integrity\u003d\"sha384-wITovz90syo1dJWVh32uuETPVEtGigN07tkttEqPv+uR2SE/mbQcG7ATL28aI9H0\" crossorigin\u003d\"anonymous\"\u003e\n \u003cscript src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.js\"\u003e\u003c/script\u003e\n \u003cscript src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/contrib/auto-render.min.js\"\u003e\u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\"\u003e// \u003c![CDATA[\r\ndocument.addEventListener(\"DOMContentLoaded\", function(){\r\n renderMathInElement(\r\n document.body,{\r\n delimiters: [\r\n {left: \"$$\", right: \"$$\", display: true},\r\n {left: \"$\", right: \"$\", display: false}]})});\r\n// ]]\u003e\u003c/script\u003e\n \u003cp\u003eLet $\\sigma_0(n)$ be the number of positive divisors of $n$.\u003c/p\u003e\n \u003cp\u003eFor example, $\\sigma_0(1) \u003d 1$, $\\sigma_0(2) \u003d 2$ and $\\sigma_0(6) \u003d 4$.\u003c/p\u003e\n \u003cp\u003eLet $$S_k(n) \u003d \\sum _{i\u003d1}^n \\sigma_0(i^k).$$\u003c/p\u003e\n \u003cp\u003eGiven $n$ and $k$, find $S_k(n) \\bmod 2^{64}$.\u003c/p\u003e\n \u003ch3\u003eInput\u003c/h3\u003e\n \u003cp\u003eThere are multiple test cases. The first line of input contains an integer $T$ ($1 \\le T \\le 10000$), indicating the number of test cases. For each test case:\u003c/p\u003e\n \u003cp\u003eThe first line contains two integers $n$ and $k$ ($1 \\le n, k \\le 10^{10}$).\u003c/p\u003e\n \u003ch3\u003eOutput\u003c/h3\u003e\n \u003cp\u003eFor each test case, output a single line containing $S_k(n) \\bmod 2^{64}$.\u003c/p\u003e\n \u003ch3\u003eExample\u003c/h3\u003e\n \u003ch4\u003eInput\u003c/h4\u003e\n \u003cpre\u003e5\r\n1 3\r\n2 3\r\n3 3\r\n10 3\r\n100 3\r\n\u003c/pre\u003e\n \u003ch4\u003eOutput\u003c/h4\u003e\n \u003cpre\u003e1\r\n5\r\n9\r\n73\r\n2302\r\n\u003c/pre\u003e\n \u003ch3\u003eInformation\u003c/h3\u003e\n \u003cp\u003eThere are 5 Input files.\u003c/p\u003e\n \u003cul\u003e\n \u003cli\u003eInput #1: $1 \\le n \\le 10000$, TL \u003d 1s.\u003c/li\u003e\n \u003cli\u003eInput #2: $1 \\le T \\le 300,\\ 1 \\le n \\le 10^7$, TL \u003d 5s.\u003c/li\u003e\n \u003cli\u003eInput #3: $1 \\le T \\le 75,\\ 1 \\le n \\le 10^{8}$, TL \u003d 5s.\u003c/li\u003e\n \u003cli\u003eInput #4: $1 \\le T \\le 15,\\ 1 \\le n \\le 10^{9}$, TL \u003d 5s.\u003c/li\u003e\n \u003cli\u003eInput #5: $1 \\le T \\le 5,\\ 1 \\le n \\le 10^{10}$ , TL \u003d 5s.\u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eMy C++ solution runs in 5.6 sec. (total time)\u003c/p\u003e\n \u003ch3\u003eNotes\u003c/h3\u003e\n \u003cp\u003eThis is general version of \u003ca href\u003d\"https://www.spoj.com/problems/DIVCNTK/DIVCNT1\"\u003eDIVCNT1\u003c/a\u003e, \u003ca href\u003d\"https://www.spoj.com/problems/DIVCNTK/DIVCNT2\"\u003eDIVCNT2\u003c/a\u003e and \u003ca href\u003d\"https://www.spoj.com/problems/DIVCNTK/DIVCNT3\"\u003eDIVCNT3\u003c/a\u003e. You may want to solve these three problems first.\u003c/p\u003e\n\u003c/div\u003e"}}]}