#PQJ1827x9612. QOJ 1827_9612

    ID: 2723 传统题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测数论

QOJ 1827_9612

标题: 月亮的背面是粉红色的 - Problem - QOJ.ac

#9612. 月亮的背面是粉红色的

Statistics

The problem was used in the following contests:

时间限制:第九个子任务时间限制 3s,第十个子任务时间限制 4s,其余子任务时间限制 2s。

题目背景

在寂静的世界里
我张开手去触碰你
想要挣脱这泥泞笨重的地心引力
我害怕的用力呼吸
期待着不可能发生的奇迹
闭上了双眼
不见 偏离的心率
无助的努力 渐渐地放弃
在残缺的内心里
哭泣着呐喊的我
现在还是散落在月球表面
等时间消逝
沉淀
我在哪里
—— 『月球偏心率』

题目描述

小 L 终于见到了月球的背面,可这里一片荒芜,冷漠乏味。

他想要把这里染成热情的粉红色,为此他翻阅数学书找到了一个函数 ft(n)=2ω(n)nt,他要根据这个函数决定染色的过程。

这里的 ω(n) 为 n 的不同质因子个数,例如 ω(1)=0,ω(2)=1,ω(8)=1,ω(6)=2。

小 L 先把这里划分成了 n×n 片区域,每个区域倒入不同数量的粉色颜料。具体来说,他会在第 i 行第 j 列的区域内倒入 ft(gcd(i,j))ft(lcm⁡(i,j)) 桶颜料。

不过他已经没有精力去计算了,因此请你直接告诉他总共需要多少桶粉色颜料。

更进一步的,如果上面的答案记成 Ft(n),小 L 会告诉你一个整数 m∈{0,1}:

  • 如果 m=0,请你输出 F0(n)。
  • 如果 m=1,请你输出 F0(n),F1(n)。

由于答案可能很大,请输出答案对 109+7 取模的值。

输入格式

一行两个整数 n,m。

输出格式

m+1 个整数,具体含义在上面。

样例输入#1
3 1
样例输出#1
25 121
样例输入#2
1000 0
样例输出#2
24870169
样例输入#3
10000000000 0
样例输出#3
213223517
样例输入#4
100000000000000 1
样例输出#4
8177545 370603117

数据规模

  • 子任务一(3 分):1≤n≤5000,m∈{0,1}。
  • 子任务二(3 分):1≤n≤107,m∈{0,1}。
  • 子任务三(8 分):1≤n≤1010,m=0。
  • 子任务四(8 分):1≤n≤1010,m∈{0,1}。
  • 子任务五(8 分):1≤n≤1012,m∈{0,1}。
  • 子任务六(10 分):1≤n≤1013,m∈{0,1}。
  • 子任务七(13 分):1≤n≤1014,m=0。
  • 子任务八(14 分):1≤n≤1014,m∈{0,1}。
  • 子任务九(16 分):1≤n≤1016,m=0。
  • 子任务十(17 分):1≤n≤1015,m∈{0,1}。

请注意子任务九和子任务十数据范围的不同。

时间限制:第九个子任务时间限制 3s,第十个子任务时间限制 4s,其余子任务时间限制 2s。