Codeforce 542 D. Superhero's Job
#C++
頗好玩的一題。
給定 $ 1 \leq n \leq 10^{12}$ ,求 $J(x) = n$ 的解的個數,其中
$$
x = p_1^{\alpha_1}p_2^{\alpha_2} \dots
$$
$$
J(x) = (1 + p_1^{\alpha_1})(1 + p_2^{\alpha_2}) \dots
$$
時限: 2000ms
主要就是枚舉出合理的因數,然後dfs或dp,因為是要求解的個數,所以用dp統計。
解法
合理的因數: 必須是 $p^\alpha+1$ ,其中 $p$ 是質數。
這就直接開 $O(\sqrt d \log d)$ 反正最差也是本身是質數。
dp
用這方式: $dp[prime][divisor]$ ,這裡面的 $prime \in P$ 就是出現在合理因數裡的質數,一個嚴謹的定義是:
$$
P = {p \ | \ p^a = n \ for \ some \ a \in \mathbb{N} }
$$
狀態轉移就會是:
$$
dp[next \ prime][divisor \times prime^a] += dp[prime][divisor] \ if \ prime^a \ | \ n
$$
實作
其實在code時快爆炸了,原本寫dfs,最大的測資一直刷不過(3???ms
),看了Tutorial才知道要用dp統計QQ
Code:
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long int int64;
typedef pair<int64, int64> pii;
int ans = 0;
vector<int64> primes;
bool seive[1000001] = {1};
vector<int64> get_div(int64 inp){
set<int64> _ret;
for(int64 lx = 1;lx*lx <= inp;lx++)
if(inp%lx == 0)
_ret.insert(lx), _ret.insert(inp/lx);
vector<int64> ret;
for(auto& it : _ret)
ret.push_back(it);
return ret;
}
typedef pair<int64,int> pi64i;
pi64i check(int64 inp){
for(int lx = 0;lx < primes.size() and primes[lx]*primes[lx] <= inp;lx++){
int64 p = primes[lx]; int c = 0;
if(inp%p == 0){
while(inp%p == 0) inp/=p, c++;
return inp == 1 ? pi64i(p,c) : pi64i(1, 0);
}
}
return pi64i(inp, 1);
}
int main(){
int64 inp; scanf("%lld", &inp);
for(int lx = 2;lx <= 1000000;lx++)
if(seive[lx] == 0){
primes.push_back(lx);
for(int ly = 2;ly*lx <= 1000000;ly++)
seive[ly*lx] = 1;
}
auto divs_tmp = get_div(inp);
map<int64,int> _pset;
for(int64 val: divs_tmp){
auto get_pc = check(val-1);
if(val > 2 and get_pc.first >= 2){
_pset[get_pc.first] = max(_pset[get_pc.first], get_pc.second);
}
}
map<int64,int> dp[2];
int now = 0; dp[0][inp] = 1;
for(auto it = _pset.begin(); it != _pset.end(); it++){
auto& pc = *it;
int64 pp = pc.first;
dp[now^1] = dp[now];
for(int cc = 1; cc <= pc.second; cc++, pp*=pc.first){
for(auto it = dp[now].begin();it != dp[now].end(); it++){
if(it->first%(pp+1) == 0){
dp[now^1][it->first/(pp+1)] += it->second;
}
}
}
now^=1;
}
printf("%d\n", dp[now][1]);
return 0;
}
|