483 字
2 分钟
BZOJ 4407 于神之怒加强版
【题目描述】
给定n,m,k,计算 对1000000007取模的结果
【输入格式】
多组数据。 第一行是两个数T,K; 之后的T行,每行两个整数n,m;
【输出格式】
K行,每行一个结果
【样例输入】
1 2
3 3
【样例输出】
20
【提示】
T<=2000,1<=N,M,K<=5000000
题解
第一步推式子
另
然后我们需要线性筛出就可以了
设
显然是积性函数
别问我怎么知道的
当互质时
当不互质时
又要推狮子
根据函数的定义
当且仅当不含平方因子时不为零
所以质因子只有选和不选两种状态,有用的状态数是不变的
每一个有用的 都乘了一个p^k;
所以
#define LL long long
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int prime[500005], tot;const int MOD = 1000000007;bool isnprime[5000005];LL g[5000005];LL primeK[500005], n, k, m;LL N = 5000000;LL pow_mod(LL a, LL b){ LL ans = 1; while (b) { if (b & 1) ans = ans * a % MOD; b >>= 1; a = a * a % MOD; } return ans;}void Get_g(){ g[1] = 1; for (int i = 2; i <= N; i++) { if (!isnprime[i]) { prime[++tot] = i; g[i] = (primeK[tot] = pow_mod(i, k)) - 1; } for (int j = 1; j <= tot; j++) { if (i * prime[j] > N) break; isnprime[i * prime[j]] = 1; if (i % prime[j] == 0) { g[i * prime[j]] = g[i] * primeK[j] % MOD; break; } g[i * prime[j]] = g[i] * g[prime[j]] % MOD; } } for (int i = 2; i <= N; i++) g[i] += g[i - 1], g[i] %= MOD;}int main(){ freopen("bzoj_4407.in","r",stdin); freopen("bzoj_4407.out","w",stdout); int t; scanf("%d%lld", &t, &k); Get_g(); while (t--) { scanf("%lld%lld", &n, &m); int last; LL ret = 0; if (n > m) swap(n, m); for (int i = 1; i <= n; i = last + 1) { last = min(n / (n / i), m / (m / i)); (ret += (n / i) * (m / i) % MOD * (g[last] - g[i - 1] + MOD) % MOD)%=MOD; } printf("%lld\n", ret); }}