题目名称	2156. [BZOJ 4407] 于神之怒加强版
输入输出	`bzoj_4407.in/out`
难度等级	★★★☆
时间限制	8000 ms (8 s)
内存限制	268 MiB
测试数据	10
题目来源	mikumikumi 于2016-02-23加入
开放分组	全部用户
提交状态
分类标签	数论莫比乌斯反演
	分享题解

通过：95，提交：193，通过率：49.22%
kito	100	2.446 s	27.98 MiB	C++
kito	100	2.793 s	27.96 MiB	C++
ajcxsu	100	3.215 s	100.45 MiB	C++
┭┮﹏┭┮	100	3.657 s	94.73 MiB	C++
半汪	100	4.157 s	119.54 MiB	C++
Go灬Fire	100	4.190 s	173.41 MiB	C++
_Itachi	100	4.356 s	40.34 MiB	C++
ajcxsu	100	4.384 s	195.82 MiB	C++
梦那边的美好ET	100	4.770 s	122.37 MiB	C++
AntiLeaf	100	4.790 s	43.21 MiB	C++

关于于神之怒加强版的近10条评论(全部评论)
Go灬Fire 2017-01-04 07:27 8楼
回复 @stdafx.h : 膜拜神犇的做法，直接掉一个log FoolMike 2017-01-02 10:24 7楼
表示本蒟蒻只会O(nlogn)的预处理+O(sqrt(n))的查询 FoolMike 2017-01-02 09:48 6楼
又是因为long long连WA2次，I'm angry!（滑稽这题结论的推导真是绝了.... 表示刚才只看得懂单次查询O(n)的....这个加强版就gg了。再去学习学习... sxysxy 2016-12-12 17:43 5楼
暴力50，鉴定完毕。 _Itachi 2016-12-11 08:46 4楼
O(n)预处理 sqrt(n)询问.... 我跑的好快 stdafx.h 2016-02-24 12:05 3楼
某OJ上的权限题x2 mikumikumi 2016-02-24 11:37 2楼
题目完全与内容无关系列.... 此外这个应该是“于神之怒加强版” Satoshi 2016-02-24 11:16 1楼

2156. [BZOJ 4407] 于神之怒加强版

★★★☆ 输入文件：bzoj_4407.in 输出文件：bzoj_4407.out 简单对比
时间限制：8 s 内存限制：268 MiB

【题目描述】

给定 $n,m,k$，计算 $\sum_{i=1}^n\sum_{j=1}^m gcd(i,j)^k$ 对 $1000000007$ 取模的结果。

【输入格式】

多组数据。

第一行是两个数 $T,K$；

之后的T行，每行两个整数 $n,m$；

【输出格式】

$K$ 行，每行一个结果。

【样例输入】

1 2
3 3

【样例输出】

【提示】

$T<=2000$，$1<=N,M,K<=5000000$。

【来源】

命题人：成都七中张耀楠

【题目来源】

BZOJ 4407