[JRKSJ R6] 牵连的世界 - 题目详情 - 33OJ

ID: 9606

远端评测题

1700ms

256MiB

难度: 9

上传者:

标签>

2022

洛谷原创

O2优化

素数判断,质数,筛法

莫比乌斯反演

背景

题目描述

给定 $n,m$ ，求

\sum_{i=1}^n \sum_{j=1}^m \sigma_0(ij)\varphi(ij)

输入格式

两个整数 $n,m$ 。

输出格式

一个整数，表示答案。答案对 $10^9+7$ 取模。

5 5

20 20

提示

$\sigma_0,\varphi$ 分别为因数个数函数，欧拉函数。

本题可能轻微卡常。

数据规模

本题采用捆绑测试。

$\text{Subtask}$	$n,m\le$	$\text{Score}$
$1$	$10^3$	$10$
$2$	$10^5$	$30$
$3$	$2\times 10^5$
$4$	$5\times 10^5$
$5$	$3\times 10^6$	$1$

对于所有数据， $1\le n,m\le 3\times 10^6$ 。

出于某些原因，你只要得到了 $\ge 100$ 分就可以通过此题。