{"problem":{"name":"「GLR-R4」夏至","description":{"content":"  为了鉴定摩柯是不是在做噩梦，请你来解决黑板上的一道简单的数学问题吧！   令积性函数 $f(n)$ 满足 $f(p^c)=p^{\\gcd(c,k)}$，其中 $k$ 为给定常数，$p$ 为素数，$c$ 为正整数。现在，给定 $n,m,k$，请求出 $$ \\left(\\sum_{i=1}^n\\sum_{j=1}^mf(i\\cdot j)\\right)\\b","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9157"},"statements":[{"statement_type":"Markdown","content":"  为了鉴定摩柯是不是在做噩梦，请你来解决黑板上的一道简单的数学问题吧！\n\n  令积性函数 $f(n)$ 满足 $f(p^c)=p^{\\gcd(c,k)}$，其中 $k$ 为给定常数，$p$ 为素数，$c$ 为正整数。现在，给定 $n,m,k$，请求出\n$$\n\\left(\\sum_{i=1}^n\\sum_{j=1}^mf(i\\cdot j)\\right)\\bmod(10^9+7).\n$$\n\n  对于积性函数的定义，请参考「题意解释」。\n\n## Input\n\n输入只有一行包含三个整数，分别表示 $n,m,k$。\n\n## Output\n\n一行一个整数，表示答案对 $10^9+7$ 取模后的值。\n\n[samples]\n\n## Background\n\n  「柳庭风静人眠昼，昼眠人静风庭柳」\n\n---\n\n  老 V 说为大家准备了特别的粽子，所以天依来了；\n\n  天依来了，所以阿绫来了；\n\n  阿绫来了，龙牙也不敢不来；\n\n  到了快一半了，于是剩下的大家都来了……\n\n  所以，为什么要在模拟演出训练结束后来补文化课啊！\n\n  “天依，这数学老师真的在讲数学？”\n\n  “摩柯，我和阿绫就靠你了！”天依戳戳前排摩柯的肩膀。\n\n  “要推出来了，要推出来了……”，摩柯大概是第一次把草稿纸写得快满，“我知道我很急，但我先别急……这像是在做噩梦一样。”\n\n---\n\n  **夏至** 「允许我这一次片刻逃离　偶尔也试着用背影　去面对未来不确定」\n\n## Note\n\n#### 题意解释\n\n  对于数论函数 $f(n)$ 和任意两个互素的正整数 $x,y$，若恒有 $f(xy)=f(x)f(y)$，则称 $f(n)$ 为积性函数。\n\n  当已知积性函数 $f(n)$ 在所有素数幂处的取值时，我们可以计算任意正整数的函数值。具体地，对于 $n>1$，设 $n$ 的**唯一分解**形式为 $n=p_1^{\\alpha_1}p_2^{\\alpha_2}\\cdots p_k^{\\alpha_k}$，则有 $f(n)=f(p_1^{\\alpha_1})f(p_2^{\\alpha_2})\\cdots f(p_k^{\\alpha_k})$。\n\n### 数据规模与约定\n\n对于 $100\\%$ 的数据，$1\\le n\\le 10^5$，$1\\le m\\le 10^{10}$，$1\\le k\\le 10^{9}$。\n\n对于不同的子任务，作如下约定：\n\n| 子任务编号 |        $n$         |      $m$      |     $k$      | 子任务分值 |\n| :--------: | :----------------: | :-----------: | :----------: | :--------: |\n|    $1$     |     $\\le 10^3$     |  $\\le 10^3$   | $\\le 10^{3}$ |    $5$     |\n|    $2$     |        $=1$        | $\\le 10^{10}$ |  $\\le 10^9$  |    $15$    |\n|    $3$     |     $\\le 10^5$     |  $\\le 10^5$   |  $\\le 10^9$  |    $15$    |\n|    $4$     |     $\\le 500$      |  $\\le 10^9$   |  $\\le 10^9$  |    $10$    |\n|    $5$     |     $\\le10^5$      | $\\le 10^{10}$ |     $=1$     |    $15$    |\n|    $6$     | $\\le 5\\times 10^3$ |  $\\le 10^9$   |  $\\le 10^9$  |    $15$    |\n|    $7$     | $\\le 5\\times 10^4$ |  $\\le 10^8$   |  $\\le 10^9$  |    $15$    |\n|    $8$     |     $\\le 10^5$     | $\\le 10^{10}$ |  $\\le 10^9$  |    $10$    |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9157","tags":["数论","洛谷原创","O2优化","素数判断,质数,筛法","莫比乌斯反演","容斥原理","洛谷月赛"],"sample_group":[["2 2 64","9"],["5 5 64 ","213"],["1234 1234 12","673319736"],["30000 10000000 2","836094021"]],"created_at":"2026-03-03 11:09:25"}}