#P3512. DZY Loves Math IV

    ID: 2724 传统题 1000ms 128MiB 尝试: 1139 已通过: 421 难度: 9 上传者: 标签>CF2600省选/NOI-欧拉函数交换求和顺序记忆化搜索杜教筛整除分块线性筛一维前缀和倍数枚举哈希表ByJc

DZY Loves Math IV

题目描述

给定 n,mn,m,求 ∑i=1n∑j=1mφ(ij)\sum_{i = 1}^{n} \sum_{j = 1}^{m} \varphi(ij) 模 109+710^9+7 的值。

输入格式

仅一行,两个整数 n,mn,m。

输出格式

仅一行答案。

100000 1000000000
857275582

数据规模

1≤n≤105,1≤m≤1091\le n \le 10^5,1\le m \le 10^9,本题共 4 组数据。

题目来源

By Jc 鸣谢杜教