我们定义
$$
J(x) = \sum _ {d | x} [\gcd(x,\frac{x}{d}) = 1] d
$$
请你求出 $J(x) = A$ 有多少个 $x$ 满足条件。
链接
Codeforces
题解
我们可以发现，这个 $J(x)$ 是一个积性函数。
所以如果 $x = {p_1}^{k_1}{p_2}^{k_2}\cdots{p_m}^{k_m}$ ，那么 $J(x) = J({p_1}^{k_1})J({p_2}^{k_2})\cdots J({p_m}^{k_m}) = ({p_1}^{k_1}+1)({p_2}^{k_2}+1)({p_m}^{k_m}+1)$
所以问题变成了我们有多少种对 $A$ 形如上面形式的不同分解。
我们考虑求出所有 $A$ 的约数，记为 $d_1,d_2,…,d_n$ 。我们考虑哪些 $p$ 可能用来组成 $A$ 。如果 $p$ 可以被用来组成 $A$ ，那么 $A$ 的约数里面肯定存在一个约数减去 $1$ 之后是 $p$ 的若干次方。
我们把所有的约数减去 $1$ 之后直接分解质因数，这个过程的复杂度大概是：
$$
\sqrt 1 + \sqrt 2 + … + \sqrt{\sqrt{n}} + \sqrt \frac{n}{1} + \sqrt{\frac{n}{2}} + … + \sqrt{\frac{n}{n}}
$$
不会证明，但可以过吧（
然后我们就得到了所有可以组成 A 的质数 $p_1,…,p_k$，这样的质数不会很多，我们发现这样的质数不会超过 $\sigma_0(n) \approx \sqrt[3]{n}$ 。
我们考虑 $dp$ , 令 $dp[i][j]$ 表示使用前 $i$ 个质数拼出来第 $j$ 个约数的方案数。
转移的话，每次加入一个质数，对于所有的 $j$，我们都乘上这个质数若干次，然后更新答案。什么？你说复杂度？不会证不会证，反正能过就行（
最后 $dp[k][n]$ 就是答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 10000;
ll A;
ll p[MAXN],k,d[MAXN],n;
map<ll,int> div_pos;set<ll> vis;
ll dp[MAXN];// 滚动数组
int main(){
cin >> A;
for(ll i = 1;i*i<=A;i++) if(A % i == 0){
d[++n] = i;
if(i * i != A) d[++n] = A/i;
}
sort(d + 1,d + n + 1);
// for(int i = 1;i<=n;i++){
// printf("%d:%lld\n",i,d[i]);
// }
for(int t = 1;t<=n;t++){
ll x = d[t]; div_pos[x] = t;x -= 1;
bool flag = 0;
for(ll i = 2;i * i <= x;i++){
if(x % i == 0){
flag = 1;
while(x % i == 0) x /= i;
if(x == 1 && !vis.count(i)) p[++k] = i,vis.insert(i);
break;
}
}
if(flag == 0 && x > 1 && !vis.count(x)) p[++k] = x,vis.insert(x);
}
sort(p+1,p+k+1);
dp[1] = 1;
for(int i = 1;i<=k;i++){
for(int j = n;j>=1;j--){
if(dp[j] == 0) continue;
for(ll w = p[i];log2(d[j]) + log2(w+1) <= log2(1.5*A);w *= p[i]){
if(div_pos.count(d[j]*(w+1))){
dp[div_pos[d[j]*(w+1)]] += dp[j];
}
}
}
}
printf("%lld\n",dp[n]);
return 0;
}
|
