2023.02.10 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

CF542D Superhero's Job。

存在 $J(x)=\sum _{k\mid x,gcd(x,\frac{x}{k})=1}k$$J(x) = \sum_{k \mid x, \gcd(x, \tfrac{x}{k}) = 1}k$，给定 $A$$A$ 求满足 $J(x)=A$$J(x) = A$ 的正整数解的个数。

模拟赛的时候像了一些奇奇怪怪的做法，大概就是想到打表，但是 $1e5$$1e5$ 的字符就会达到 100KiB 的限制，无法通过，但是经过找规律可以用字符代替 $[0,52]$$[0, 52]$ 的数，其它数可以额外记录，然后发现有大量连续的 $0$$0$ 等，考虑将形如 ##### 压成 5#，最终展开即可，这样最终打出来了约 $1.6e5$$1.6e5$ 的答案，多出来的 $6e5$$6e5$ 打的是最接近 $1e7$$1e7$ 的部分数，当然最后都挂了，$20\mathtt{\text{pts}}$$20\texttt{pts}$。

Code（生成器）

​x
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template < typename T = int >
26
inline T read(void);
27

28
ll F(ll x){
29
    if(x == 1)return 1;
30
    ll ret(0);
31
    for(ll i = 1; i * i <= x; ++i)
32
        if(!(x % i) && __gcd(i, x / i) == 1)ret += i + x / i;
33
    return ret;
34
    // printf("f(%lld) = %lld%s", x, ret, x % 10 == 0 ? "\n" : "; ");
35
}
36
map < ll, ll > cnt;
37
map < char, int > mp;
38
map < int, char > rmp;
39
map < ll, ll > unex;
40

41
int main(){
42
    freopen("out.txt", "w", stdout);
43
    fprintf(stderr, "Begin to build map...\n");
44
    mp['#'] = 0, rmp[0] = '#';
45
    printf("mp['#']=0;");
46
    for(int i = 1; i <= 26; ++i){
47
        mp['a' + i - 1] = i, rmp[i] = 'a' + i - 1,
48
        printf("mp['%c']=%d;", char('a' + i - 1), i);
49
    }printf("\n");
50
    for(int i = 1; i <= 26; ++i){
51
        mp['A' + i - 1] = i + 26, rmp[i + 26] = 'A' + i - 1,
52
        printf("mp['%c']=%d;", char('A' + i - 1), i + 26);
53
    }printf("\n\n\n");
54
    fprintf(stderr, "Begin to cal f(x)...\n");
55
    for(int i = 1; i <= 11000000; ++i)cnt[F(i)]++;
56
    fprintf(stderr, "Complete.\n");
57
    // printf("string ans = \"#");
58
    string ans; ans += '#';
59
    for(int i = 1; i <= 100000; ++i){
60
        if(rmp.find(cnt[i]) == rmp.end())unex[i] = cnt[i], ans += '*';//printf("#");
61
        else ans += rmp[cnt[i]];//printf("%c", rmp[cnt[i]]);
62
    }
63
    // printf("\";\n\n");
64
    {
65
        printf("string ans = \"");
66
        char lst('@'); int cnt(0);
67
        for(auto it = ans.begin(); it != ans.end(); ++it){
68
            if(lst == '@' || *it == lst){
69
                if(cnt == 9)printf("%d%c", cnt, lst), cnt = 0;
70
                lst = *it, ++cnt;
71
            }else{
72
                if(cnt == 1)printf("%c", lst);
73
                else printf("%d%c", cnt, lst);
74
                lst = *it, cnt = 1;
75
            }
76
        }if(cnt != 1)printf("%d%c", cnt, lst);
77
        else printf("%c", lst);
78
        printf("\";\n\n");
79
    }
80
    //begin at 9940000
81
    string bans;
82
    // printf("string bans = \"");
83
    for(int i = 9940000; i <= 10000000; ++i){
84
        if(rmp.find(cnt[i]) == rmp.end())unex[i] = cnt[i], bans += '*';
85
        // fprintf(stderr, "Find unexist ans ans[%d] = %lld\n", i, cnt[i]), bans += '*';//, printf("#");
86
        else bans += rmp[cnt[i]];//printf("%c", rmp[cnt[i]]);
87
    }
88

89
    {
90
        printf("string bans = \"");
91
        char lst('@'); int cnt(0);
92
        for(auto it = bans.begin(); it != bans.end(); ++it){
93
            if(lst == '@' || *it == lst){
94
                if(cnt == 9)printf("%d%c", cnt, lst), cnt = 0;
95
                lst = *it, ++cnt;
96
            }else{
97
                if(cnt == 1)printf("%c", lst);
98
                else printf("%d%c", cnt, lst);
99
                lst = *it, cnt = 1;
100
            }
101
        }if(cnt != 1)printf("%d%c", cnt, lst);
102
        else printf("%c", lst);
103
        printf("\";\n\n");
104
    }
105
    // }printf("\";\n\n");
106

107
    // for(auto mp : cnt){printf("Ans[ %lld ] = %lld\n", mp.first, mp.second);}
108

109
    for(auto mp : unex){
110
        printf("u[%lld]=%lld;", mp.first, mp.second);
111
    }printf("\n\n");
112

113
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
114
    return 0;
115
}
116

117
template < typename T >
118
inline T read(void){
119
    T ret(0);
120
    int flag(1);
121
    char c = getchar();
122
    while(c != '-' && !isdigit(c))c = getchar();
123
    if(c == '-')flag = -1, c = getchar();
124
    while(isdigit(c)){
125
        ret *= 10;
126
        ret += int(c - '0');
127
        c = getchar();
128
    }
129
    ret *= flag;
130
    return ret;
131
}

Code（主程序）

xxxxxxxxxx
95
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template < typename T = int >
26
inline T read(void);
27

28
map < char, int > mp;
29
map < int, int > u;
30

31

32
string ans = "#a#4a#3a#b#a2#ab#b3#c.....#b9#2#a5#c#a#a#a3#k";
33

34
string bans = "I#a#a3#a7#a3#c7#a3#j3#a3#c3#b5#a9#a7#a9#2#l5#a5#a#a#e3......#g9#a#a#a#a3#a9#a#b3#a3#v";
35

36
//篇幅过长省略
37

38
string rans, rbans;
39
int main(){
40
    freopen("number.in", "r", stdin);
41
    freopen("number.out", "w", stdout);
42

43

44
    mp['#']=0;mp['a']=1;mp['b']=2;mp['c']=3;mp['d']=4;mp['e']=5;mp['f']=6;mp['g']=7;mp['h']=8;mp['i']=9;mp['j']=10;mp['k']=11;mp['l']=12;mp['m']=13;mp['n']=14;mp['o']=15;mp['p']=16;mp['q']=17;mp['r']=18;mp['s']=19;mp['t']=20;mp['u']=21;mp['v']=22;mp['w']=23;mp['x']=24;mp['y']=25;mp['z']=26;
45
    mp['A']=27;mp['B']=28;mp['C']=29;mp['D']=30;mp['E']=31;mp['F']=32;mp['G']=33;mp['H']=34;mp['I']=35;mp['J']=36;mp['K']=37;mp['L']=38;mp['M']=39;mp['N']=40;mp['O']=41;mp['P']=42;mp['Q']=43;mp['R']=44;mp['S']=45;mp['T']=46;mp['U']=47;mp['V']=48;mp['W']=49;mp['X']=50;mp['Y']=51;mp['Z']=52;
46

47
    u[8640]=63;u[10080]=65;u[11520]=60;u[12096]=54;u[12960]=71;u[14400]=69;u[15120]=69;u[17280]=88;u[18144]=57;u[20160]=89;u[21600]=81;u[23040]=67;u[23760]=56;u[24192]=67;u[24480]=59;u[25200]=78;u[25920]=102;u[26880]=53;u[27360]=56;u[28800]=81;u[30240]=121;u[31680]=73;u[32256]=53;u[32400]=78;u[33600]=65;u[34560]=118;u[35280]=60;u[36000]=68;u[36288]=84;u[36720]=55;u[37440]=62;u[37800]=58;u[38880]=87;u[40320]=122;u[41040]=63;u[41472]=56;u[42336]=66;u[43200]=131;u[44352]=55;u[45360]=104;u[46080]=87;u[47520]=96;u[48384]=94;u[48960]=78;u[50400]=109;u[51840]=144;u[52416]=56;u[53760]=66;u[54000]=71;u[54432]=72;u[54720]=88;u[55440]=78;u[56160]=85;u[56448]=59;u[57024]=61;u[57456]=56;u[57600]=116;u[58320]=54;u[58752]=54;u[60480]=188;u[61200]=69;u[62208]=66;u[63360]=100;u[63504]=58;u[64512]=66;u[64800]=126;u[65280]=63;u[65520]=68;u[65664]=71;u[66528]=74;u[67200]=83;u[68040]=56;u[68400]=57;u[68544]=57;u[69120]=149;u[70560]=101;u[71280]=81;u[72000]=94;u[72576]=116;u[72960]=55;u[73440]=95;u[73920]=72;u[74880]=90;u[75600]=136;u[76032]=69;u[76608]=71;u[76800]=58;u[77760]=143;u[78624]=71;u[79200]=90;u[80640]=160;u[81600]=62;u[82080]=100;u[82944]=79;u[83160]=59;u[84000]=73;u[84240]=72;u[84672]=91;u[85536]=57;u[85680]=74;u[86400]=179;u[87360]=74;u[87552]=55;u[88128]=56;u[88704]=75;u[89280]=62;u[89856]=57;u[90000]=55;u[90720]=190;u[91200]=59;u[92160]=100;u[92400]=60;u[93312]=58;u[93600]=85;u[94080]=70;u[95040]=143;u[95760]=83;u[96000]=56;u[96768]=115;u[97200]=96;u[97920]=119;u[98280]=60;u[98496]=78;u[99360]=56;u[99792]=67;u[99840]=56;u[9940320]=193;u[9940800]=78;u[9941760]=59;u[9942912]=160;u[9943560]=87;u[9944064]=69;u[9945000]=100;u[9945600]=300;u[9945936]=90;u[9946800]=92;u[9947040]=57;u[9947448]=54;u[9947520]=196;u[9948400]=57;u[9948672]=55;u[9948960]=309;u[9950400]=96;u[9950976]=69;u[9951120]=88;u[9952200]=64;u[9952800]=125;u[9953280]=1110;u[9953568]=61;u[9954000]=115;u[9955200]=200;u[9956520]=75;u[9956736]=54;u[9957600]=90;u[9958080]=56;u[9958464]=72;u[9959040]=816;u[9959760]=123;u[9960000]=97;u[9960192]=125;u[9960720]=77;u[9961056]=155;u[9961920]=84;u[9962400]=63;u[9962496]=81;u[9963000]=97;u[9963360]=229;u[9963648]=83;u[9964800]=190;u[9966240]=64;u[9966528]=99;u[9966600]=53;u[9967104]=200;u[9968112]=74;u[9968400]=122;u[9968640]=69;u[9969120]=153;u[9969480]=60;u[9969600]=59;u[9970128]=91;u[9970560]=134;u[9971520]=116;u[9972480]=185;u[9972720]=130;u[9973152]=116;u[9974016]=262;u[9975168]=59;u[9975600]=79;u[9976320]=67;u[9977760]=146;u[9979200]=1789;u[9980928]=252;u[9982440]=62;u[9983232]=69;u[9983520]=65;u[9984000]=321;u[9984240]=55;u[9984384]=122;u[9984480]=56;u[9984576]=72;u[9984600]=66;u[9985248]=136;u[9985680]=80;u[9985920]=61;u[9986400]=93;u[9987120]=86;u[9987600]=102;u[9987840]=606;u[9989280]=80;u[9989568]=72;u[9989760]=84;u[9990000]=179;u[9990288]=87;u[9991296]=140;u[9991800]=79;u[9991872]=60;u[9992160]=113;u[9993600]=103;u[9993984]=149;u[9994320]=82;u[9994752]=67;u[9995328]=59;u[9995520]=91;u[9996000]=232;u[9996480]=130;u[9997344]=228;u[9998208]=90;u[9998640]=57;u[9999360]=652;
48

49

50

51

52
    for(auto it = ans.begin(); it != ans.end(); ++it){
53
        if(!isdigit(*it))rans += *it;
54
        else{
55
            int cnt = *it - '0';
56
            advance(it, 1);
57
            for(int i = 1; i <= cnt; ++i)rans += *it;
58
        }
59
    }
60
    for(auto it = bans.begin(); it != bans.end(); ++it){
61
        if(!isdigit(*it))rbans += *it;
62
        else{
63
            int cnt = *it - '0';
64
            advance(it, 1);
65
            for(int i = 1; i <= cnt; ++i)rbans += *it;
66
        }
67
    }
68
    // cout << rans;
69
    ll N = read < ll >();
70
    if((100000ll < N && N < 9940000ll) || N > 10000000ll)printf("%d\n", rnddd(50) ? 1 : 0), exit(0);
71
    if(u.find((int)N) != u.end())printf("%d\n", u[(int)N]);
72
    else{
73
        if(N <= 100000)printf("%d\n", mp[rans.at(N)]);
74
        else printf("%d\n", mp[rbans.at(N - 9940000)]);
75
    }
76
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
77
    return 0;
78
}
79

80
template < typename T >
81
inline T read(void){
82
    T ret(0);
83
    int flag(1);
84
    char c = getchar();
85
    while(c != '-' && !isdigit(c))c = getchar();
86
    if(c == '-')flag = -1, c = getchar();
87
    while(isdigit(c)){
88
        ret *= 10;
89
        ret += int(c - '0');
90
        c = getchar();
91
    }
92
    ret *= flag;
93
    return ret;
94
}
95

T2

给定 $n,m$$n, m$，求长度为 $n$$n$ 的每个数值域在 $[1,m]$$[1, m]$ 的所有序列的本质不同序列（包括空序列）数之和。

赛时没啥思路，拿了 $10\mathtt{\text{pts}}$$10\texttt{pts}$ 暴力分和 $10\mathtt{\text{pts}}$$10\texttt{pts}$ 的性质分。

Code

xxxxxxxxxx
83
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (ll)(1e9 + 7)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N, M;
29
ll ans(0);
30
basic_string < int > arr;
31
basic_string < int > sub;
32
set < basic_string < int > > exist;
33

34
void dfs_sub(int dep = 1){
35
    if(dep > N){
36
        if(exist.find(sub) == exist.end())++ans, exist.insert(sub);
37
        return;
38
    }
39
    sub += arr.at(dep - 1);
40
    dfs_sub(dep + 1);
41
    sub.pop_back();
42
    dfs_sub(dep + 1);
43
}
44

45
void Cal(void){
46
    exist.clear();
47
    dfs_sub();
48
    ans %= MOD;
49
}
50

51
void dfs(int dep = 1){
52
    if(dep > N)return Cal();
53
    for(int i = 1; i <= M; ++i)
54
        arr += i, dfs(dep + 1), arr.pop_back();
55
}
56

57
int main(){
58
    freopen("sequence.in", "r", stdin);
59
    freopen("sequence.out", "w", stdout);
60
    N = read(), M = read();
61
    if((ll)N * M > (ll)1e6)exit(1);
62
    if(M == 1)printf("%d\n", N + 1), exit(0);
63
    dfs();
64
    printf("%lld\n", ans);
65
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66
    return 0;
67
}
68

69
template < typename T >
70
inline T read(void){
71
    T ret(0);
72
    int flag(1);
73
    char c = getchar();
74
    while(c != '-' && !isdigit(c))c = getchar();
75
    if(c == '-')flag = -1, c = getchar();
76
    while(isdigit(c)){
77
        ret *= 10;
78
        ret += int(c - '0');
79
        c = getchar();
80
    }
81
    ret *= flag;
82
    return ret;
83
}

T3

LG-P6326 Shopping。

给定树形结构，每个点代表商店，有 $d_i$$d_i$ 个价格为 $c_i$$c_i$ 喜爱度为 $w_i$$w_i$ 的商品，特别地，若在 $u,v$$u, v$ 商店买了东西则在 $u,v$$u, v$ 路径上的所有商店都必须买东西，共有 $m$$m$ 元，最大化买到商品的喜爱度，输出最大值。

这题也想了挺久的，最终能想到的思路是 有依赖的多重背包，然后就不太会写了，实际上还是数据范围看的有点问题，否则这个东西直接把多重背包无脑一点做 $50\mathtt{\text{pts}}$$50\texttt{pts}$ 应该是能拿到的，后面的性质分也不是很难，总之最后这道题直接挂了。

正解

T1

首先 $J(x)$$J(x)$ 是个不完全积性函数，这里尝试（可能不严谨）详细地说一下：

首先考虑若我们将 $x$$x$ 质因数分解为 $x=\prod p_i^{k_i}$$x = \prod p_i^{k_i}$ 的形式，那么枚举其因数就相当于是枚举其所有质因子所有不同幂次能够组成的所有数 $k$$k$，而对应的 ${\displaystyle \frac{x}{k}}$$\dfrac{x}{k}$ 也就是剩下的质因数合起来，于是问题转化为将所有质因数划分为两个可空的集合，而考虑 $k\perp {\displaystyle \frac{x}{k}}$$k \perp \dfrac{x}{k}$ 的条件，其可以转化为两数质因数分解后无相同质因子，于是我们不难发现对于 $x$$x$ 分解出的 $p_i$$p_i$，每一个集合中要么有全部的 $p_i$$p_i$ 要么没有 $p_i$$p_i$，否则两个集合将会有公因子 $p_i$$p_i$。于是最终问题转化为将质因子种类数进行可空地划分。这时我们想到，如果 $a\perp b$$a \perp b$，那么 $a,b$$a, b$ 质因数分解出来的质因子一定完全不同，那么假设 $a$$a$ 有 $x$$x$ 种，$b$$b$ 有 $y$$y$ 种，$a\times b$$a \times b$ 就一定有 $x+y$$x + y$ 种，所以从 $x$$x$ 种里选择 $[0,x]$$[0, x]$ 的所有方案乘上 $y$$y$ 种里选择 $[0,y]$$[0, y]$ 的所有方案一定等价于从 $x+y$$x + y$ 种里选择 $[0,x+y]$$[0, x + y]$ 的方案，这个可以从类似组合意义的思想上去考虑，所以一定有 $J(a\times b)=J(a)\times J(b)(a\perp b)$$J(a \times b) = J(a) \times J(b) (a \perp b)$。

于是不难发现对于质数 $p$$p$，有 $J(p)=p+1$$J(p) = p + 1$，更具体地说应为 $J(p^k)=p^k+1$$J(p^k) = p^k + 1$，所以当我们对 $x$$x$ 分解为 $x=\prod p_i^{k_i}$$x = \prod p_i^{k_i}$ 时 $J(x)$$J(x)$ 就变为了 $J(x)=\prod (p_i^{k_i}+1)$$J(x) = \prod (p_i^{k_i} + 1)$。

至此不难想到，我们现在已知 $J(x)=A$$J(x) = A$，那么只需要找到所有 $A=\prod (p_i^{k_i}+1)$$A = \prod (p_i^{k_i} + 1)$ 的分解方案，就会一一对应着 $x$$x$ 的分解方案，也就是说分解方案的个数就是最终的答案。

考虑如何分解，显然对于 $1e12$$1e12$ 的范围根号分治是一个显而易见的想法，考虑枚举 $1e6$$1e6$ 以内的所有质数，及其范围内的若干次方丢到 unordered_map 里，同时需要记录基于的质数，而若其存在 $1e6$$1e6$ 以外的因子，那么一定最多为一次方，反之 $p^2+1$$p^2 + 1$ 就会超过 $1e12$$1e12$ 从而超过范围。

于是可以考虑根号枚举 $A$$A$ 的所有因数，$1e6$$1e6$ 内的直接查一下之前预处理的里面有没有，反之判断其减 $1$$1$ 后是否为质数即可。

此时可以通过背包处理，即 $dp(i,j)$$dp(i, j)$ 表示考虑前 $i$$i$ 个质数（及其若干次方）能够凑成 $j$$j$ 的方案数，转移显然，同时注意整个 $dp$$dp$ 数组是需要离散下来的，也就是可以通过 unordered_map 维护，而记录基于某个质数便是为了在转移的时候不出现同时使用多个质数的情况，所以对每个质数开个 basic_string 记录其所有合法的 $p^k$$p^k$，具体来说这里也需要离散化，可以套个 unordered_map。

尝试分析复杂度，考虑 DP 时，显然枚举素数时最多有 $d(n)$$d(n)$，我们在 DP 过程中第二维枚举直接用前一维的状态和新的质数合并，这样合并之后的数一定亦为 $n$$n$ 的因子，故这一维也是 $d(n)$$d(n)$，则 DP 的复杂度为 $d^2(n)$$d^2(n)$，前面不论是线性筛亦或是枚举因数均为 $\sqrt{n}$$\sqrt{n}$ 的，对于 $x$$x$ 的 Miller-Rabin 朴素地进行 $k$$k$ 轮测试的复杂度为 $k\log x$$k\log x$，我们会对约 ${\displaystyle \frac{d(n)}{2}}$$\dfrac{d(n)}{2}$ 个数进行测试。则最终复杂度 $O(\sqrt{n}+d(n)(d(n)+k\log n))$$O(\sqrt{n} + d(n)(d(n) + k\log n))$。

Tips：注意计算过程中包括但不限于 Miller-Rabin 有多处会超过 long long 范围，需要开 __int128_t 或用 long double 快速乘，可以通过 Sanitizer 检测 signed-integer-overflow 并输入最大的数据进行测试寻找报错。

Code

xxxxxxxxxx
123
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (1100000)
24

25
template < typename T = int >
26
inline T read(void);
27

28
ll N;
29
unordered_map < ll, ll > dp[2];
30
basic_string < ll > Prime;
31
unordered_map < ll, ll > pows;
32
bitset < LIM + 100 > notPrime;
33
unordered_map < ll, basic_string < ll > > tpow;
34
basic_string < ll > tot;
35

36
namespace MillerRabin{
37
    int radix[10] = {0,  2, 3, 5, 7, 11, 13, 19, 17};
38
    ll qpow(ll a, ll b, ll MOD){
39
        ll ret(1), mul(a);
40
        while(b){
41
            if(b & 1)ret = (__int128_t)ret * mul % MOD;
42
            b >>= 1;
43
            mul = (__int128_t)mul * mul % MOD;
44
        }return ret;
45
    }
46
    bool Check(ll N){
47
        if(N <= 2 || !(N & 1))return N == 2;
48
        ll base(N - 1); int cpow(0);
49
        while(base % 2 == 0)base >>= 1, ++cpow;
50
        for(int t = 1; t <= 8; ++t){
51
            ll cur = qpow(radix[t], base, N);
52
            if(cur == 1)continue;
53
            for(int i = 1; i <= cpow; ++i){
54
                if(cur == N - 1)break;
55
                cur = (__int128_t)cur * cur % N;
56
                if(i == cpow)return false;
57
            }
58
        }return true;
59
    }
60
};
61

62
void Sieve(void){
63
    for(ll i = 2; i <= LIM; ++i){
64
        if(!notPrime[i])Prime += i;
65
        for(auto p : Prime){
66
            if(p * i > LIM)break;
67
            notPrime[p * i] = true;
68
            if(i % p == 0)break;
69
        }
70
    }
71
}
72
void Init(void){
73
    Sieve();
74
    for(auto p : Prime){
75
        ll base(p);
76
        while(base <= N)pows[base] = p, base *= p;
77
    }
78
    for(ll i = 1; i * i <= N; ++i){
79
        if(N % i)continue;
80
        if(pows.find(i - 1) != pows.end())
81
            tpow[pows[i - 1]] += i, tot += pows[i - 1];
82
        if(i * i != N){
83
            if(pows.find(N / i - 1) != pows.end())
84
                tpow[pows[N / i - 1]] += N / i, tot += pows[(N / i) - 1];
85
            else if(MillerRabin::Check(N / i - 1))
86
                tpow[N / i - 1] += N / i, tot += N / i - 1;
87
        }
88
    }
89
    sort(tot.begin(), tot.end());
90
    tot.erase(unique(tot.begin(), tot.end()), tot.end());
91
}
92

93
int main(){
94
    N = read < ll >();
95
    Init();
96
    dp[0][1] = 1;
97
    int base(0);
98
    for(auto p : tot){
99
        base ^= 1, dp[base] = dp[base ^ 1];
100
        for(auto lst : dp[base ^ 1])
101
            for(auto pri : tpow[p])
102
                if((__int128_t)pri * lst.first <= N && N % (pri * lst.first) == 0)
103
                    dp[base][pri * lst.first] += lst.second;
104
    }printf("%lld\n", dp[base][N]);
105
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
106
    return 0;
107
}
108

109
template < typename T >
110
inline T read(void){
111
    T ret(0);
112
    int flag(1);
113
    char c = getchar();
114
    while(c != '-' && !isdigit(c))c = getchar();
115
    if(c == '-')flag = -1, c = getchar();
116
    while(isdigit(c)){
117
        ret *= 10;
118
        ret += int(c - '0');
119
        c = getchar();
120
    }
121
    ret *= flag;
122
    return ret;
123
}

T2

存在一些高妙推导，可以从奇怪的组合意义或者二项式反演得到，最终可以任意模数 NTT 优化，总是很高秒就对了。

T3

点分治 + 背包，先去复习一下点分治再来补。

UPD

update-2023_02_10 初稿