XTCPC2019 F.Neko and function
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=6537
题目大意
定义 $f(n, k)$ 为选择 $k$ 个数 $a_i,(a_i > 1)$ ，使得有 $\prod\limits_{k=1}{a_i} = n$。求 $\sum_{i = 1} ^ {n} f(i,k)$ 。
注意如果 $n = 6$ ，那么 $6 = 2 \times 3$ 和 $6 = 3 \times 2$ 算作不同的方法。结果对 $10 ^ 9 + 7$ 取模。
题目分析
设 $g(n, k)$ 为选择 $k$ 个大于等于 $1$ 的数使得乘积为 $n$ 的方法数。那么根据容斥原理，有 $f(n, k) = \sum\limits_{i=1}^k{(-1) ^ i g(n, k – i) C_{k}^i}$
而 $g(n, k)$ 显然可以考虑为将所有的质因子放入 $k$ 个框有多少种放法，因此有 $g(n, k) = \prod{C_{a_i + k – 1}^{a_i}}$ ，其中 $a_i$ 为第 $i$ 个质因子出现的次数。
显然 $g(n, k)$ 为积性函数，因此可以使用 min_25 筛。
现场给的时限是单点 $8s$ ，总时限 $150s$ 。但是 $HDU$ 上给的时限是多组数据单点 $10s$。因此第一遍写完 $TLE$ 了还得优化……
考虑到每次筛的时候的预处理其实只是多乘了个 $C_{k}^{1}$，因此可以把它先提出来预处理一遍之后每次运算时乘上 $C_{k}^{1}$ 。
之后为了减少使用取模，代码中用了 $int128$ ……不过现场赛的时候应该是不用加这两个优化的。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 1e5 + 5;
int N = 1e5;
int mod = 1e9 + 7;
int n, m, t;
int prime[maxn];
bool isnp[maxn];
int p[maxn];
int pc = 0;
int id[maxn];
int id2[maxn];
int w[maxn];
int wc;
int h[maxn];
int g[maxn];
int fac[maxn];
int inv[maxn];
long long qpow(long long b, int x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
b = b * b % mod;
x >>= 1;
}
return ret;
}
int getc(int x, int y){
if(y > x)return 0;
return 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;
}
int F(int b, int x){
return h[x];
}
int init(){
int i, j;
pc = 0;
memset(isnp, 0, sizeof(isnp));
for(i=2;i<=N;i++){
if(!isnp[i]){
pc++;
prime[pc] = i;
p[pc] = p[pc - 1] + 1;
}
for(j=1;j<=pc and i * prime[j]<=N;j++){
isnp[i * prime[j]] = true;
if(i % prime[j] == 0){
break;
}
}
}
return 0;
}
int getid(int x){
if(x <= N){
return id[x];
}else{
return id2[n / x];
}
}
int pre(){
int i, j;
wc = 0;
for(i=1;i<=n;i=j+1){
j = n / (n / i);
w[++wc] = n / i;
if(w[wc] <= N){
id[w[wc]] = wc;
}else{
id2[n / w[wc]] = wc;
}
g[wc] = w[wc] - 1;
}
for(j=1;j<=pc;j++){
for(i=1;i<=wc and 1ll*prime[j]*prime[j]<=w[i];i++){
int k = getid(w[i] / prime[j]);
g[i] += mod - (g[k] - p[j - 1]);
if(g[i] >= mod)g[i] -= mod;
}
}
return 0;
}
int sum(int x, int i){
if(x <= 1 or prime[i] > x)return 0;
int k = getid(x);
__int128 ret = 1ll * (g[k] - p[i - 1]) * F(2, 1);
for(int j=i;j<=pc and prime[j]*prime[j]<=x;j++){
for(int e=1,r=prime[j];1ll*r*prime[j]<=x;e++,r*=prime[j]){
ret = (ret + 1ll * F(prime[j], e) * sum(x / r, j + 1) + F(prime[j], e + 1));
}
}
ret %= mod;
return ret;
}
int main(){
int i, j;
int ans = 0;
fac[0] = inv[0] = 1;
for(i=1;i<=1e5;i++){
fac[i] = 1ll * fac[i - 1] * i % mod;
inv[i] = qpow(fac[i], mod - 2);
}
while(cin >> n >> m){
N = sqrt(n);
ans = 0;
init();
pre();
t = 1;
ans = (ans + qpow(-1, m - t) * (n - 1) * getc(m, m - t) % mod) % mod;
for(t=2;t<=m;t++){
h[0] = 1;
for(i=1;i<=30;i++){
h[i] = 1ll * h[i - 1] * (i + t - 1) % mod * inv[i] % mod * fac[i - 1] % mod;
}
ans = (ans + qpow(-1, m - t) * sum(n, 1) * getc(m, m - t) % mod) % mod;
}
cout << (ans % mod + mod) % mod << endl;
}
return 0;
}