我们定义
请你求出 有多少个 满足条件。
链接🔗
Codeforces
题解🔗
我们可以发现,这个 是一个积性函数。
所以如果 ,那么
所以问题变成了我们有多少种对 形如上面形式的不同分解。
我们考虑求出所有 的约数,记为 。我们考虑哪些 可能用来组成 。如果 可以被用来组成 ,那么 的约数里面肯定存在一个约数减去 之后是 的若干次方。
我们把所有的约数减去 之后直接分解质因数,这个过程的复杂度大概是:
不会证明,但可以过吧(
然后我们就得到了所有可以组成 A 的质数 ,这样的质数不会很多,我们发现这样的质数不会超过 。
我们考虑 , 令 表示使用前 个质数拼出来第 个约数的方案数。
转移的话,每次加入一个质数,对于所有的 ,我们都乘上这个质数若干次,然后更新答案。什么?你说复杂度?不会证不会证,反正能过就行(
最后 就是答案。
代码🔗
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;
}
|