「LibreOJ Round #11」Misaka Network 与求和 - 题目

首页题库比赛评测排名讨论帮助

内存限制：512 MiB 时间限制：4000 ms 标准输入输出

题目类型：传统评测方式：文本比较

上传者： cz_xuyixuan

提交提交记录统计讨论测试数据附加文件

一方通行成功接入了 Misaka Network。

现在他要使用超能力，自然计算式被送到了御坂网络进行处理。这次的计算式式这样子的：

$N \sum i = 1 N \sum j = 1 f (gcd (i, j))^{k} mod 2^{32}$

其中 $f (x)$ 表示 $x$ 次大的质因数，重复的质因数计算多次，例如 $f (6) = 2, f (4) = 2$ 。规定 $f (1) = 0, f (p) = 1$ ，其中 $p$ 为质数。

但是妹妹们都不会算这个式子……所以御坂 20001 号找到了你，希望你帮她算一下。

一行两个正整数 $N$ 和 $k$ 。

一行一个整数，表示答案。

4 2

666 233

2539518298

对于所有数据 $\leq N,k \leq 2 \times 10^9$ 。

子任务编号	分值	$N$	$k$
1	$5$	$≤1000\leq 1000$	$≤2×109\leq2 \times 10^9$
2	$12$	$≤105\leq 10^5$	$≤2×109\leq2 \times 10^9$
3	$18$	$≤107\leq 10^7$	$≤2×109\leq2 \times 10^9$
4	$15$	$≤2×109\leq 2 \times 10^9$	$= 1$
5	$50$	$≤2×109\leq 2 \times 10^9$	$≤2×109\leq 2 \times 10^9$

或者，上传代码文件

LibreOJ Powered by SYZOJ.

#572. 「LibreOJ Round #11」Misaka Network 与求和