#P4407. 于神之怒加强版

    ID: 3612 传统题 2000ms 512MiB 尝试: 2083 已通过: 620 难度: 7 上传者: 标签>CF2200提高+/省选-莫比乌斯反演狄利克雷卷积交换求和顺序筛法计算积性函数快速幂一维前缀和整除分块

于神之怒加强版

题目描述

给定 n,m,kn,m,k,求

$$\sum^{n}_{i=1} \sum^{m}_{j=1} \gcd(i,j)^k\ \bmod(10^9+7)$$

输入格式

输入有多组数据,输入数据的第一行两个正整数 T,kT,k,代表有 TT 组数据,kk 的意义如上所示。

下面第二行到第 T+1T+1 行,每行为两个正整数 n,mn,m,其意义如上式所示。

输出格式

输出一个整数。

1 2
3 3 
20

数据规模与约定

对于 100%100\% 的数据,1≤n,m,k≤5×106,1≤T≤20001\le n,m,k\le 5\times 10^6,1\le T\le 2000。

题目来源

命题人:成都七中张耀楠,鸣谢 excited 上传。