{"problem":{"name":"「SvR-2」Let's Meet at a Higher Place","description":{"content":"构造一个长为 $m$ 的整数序列 $a$，使 $\\forall 1 \\leq i \\leq m$，$a_i \\in [1, n]$。 求出其前缀 $\\gcd$，记为整数序列 $b$。 $f(n, m, k)$ 的值为可以通过如上方式构造出的 $b$ 序列中**相邻项相等的情况出现次数 $\\leq k$** 的**不同**的 $b$ 序列的个数。 给定正整数 $n, m$，小 L 请你帮他求出","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9091"},"statements":[{"statement_type":"Markdown","content":"构造一个长为 $m$ 的整数序列 $a$，使 $\\forall 1 \\leq i \\leq m$，$a_i \\in [1, n]$。\n\n求出其前缀 $\\gcd$，记为整数序列 $b$。\n\n$f(n, m, k)$ 的值为可以通过如上方式构造出的 $b$ 序列中**相邻项相等的情况出现次数 $\\leq k$** 的**不同**的 $b$ 序列的个数。\n\n给定正整数 $n, m$，小 L 请你帮他求出 $\\displaystyle\\sum_{i = 1}^n \\sum_{j = 1}^m \\sum_{k = 0}^{j - 1} f(\\lfloor \\frac{n}{i} \\rfloor, j, k)$ 的值。\n\n由于结果可能很大，所以你只需要求出结果对 $2^{32}$ 取模的值。\n\n## Input\n\n一行，两个整数 $n, m$。\n\n## Output\n\n一行，一个整数，表示所求的值。\n\n[samples]\n\n## Background\n\n$$「有朝一日，让我们相逢在更高处！」$$\n\n## Note\n\n| $\\bf{Subtask}$ | $n$ | $m$ | 分值 |\n| :------: | :------: | :------: | :------: |\n| $1$ | $1 \\leq n \\leq 10^4$ | 无特殊限制 | $10 \\operatorname{pts}$ |\n| $2$ | $1 \\leq n \\leq 10^6$ | 同上 | $20 \\operatorname{pts}$ |\n| $3$ | $1 \\leq n \\leq 10^9$ | 同上 | $20 \\operatorname{pts}$ |\n| $4$ | 无特殊限制 | $1 \\leq m \\leq 25$ | $20 \\operatorname{pts}$ |\n| $5$ | 同上 | 无特殊限制 | $30 \\operatorname{pts}$ |\n\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 10^{10}$，$1 \\leq m \\leq 34$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9091","tags":["递推","2023","数论","洛谷原创","O2优化","素数判断,质数,筛法","排列组合","容斥原理","洛谷月赛","根号分治"],"sample_group":[["4 2","26"]],"created_at":"2026-03-03 11:09:25"}}