数学基础问题

Again Prime? No time.

  • n!n! 进行阶乘分解,对某个素因子pp, 其分解为presp^{\text{res}}
  • mm 进行素因子分解,并且求出和阶乘素因子的交集

    (pe)k=resansminrese\left(p^e\right)^k = \text{res} \quad ans \leftarrow \min \left\lfloor \frac{\text{res}}{e} \right\rfloor

    注意这里即使res<e\text{res} < e 也没有关系,res<e\text{res} < e 意味着res/e=0\left\lfloor \text{res}/e \right\rfloor = 0
    ans=0, ans=ans = 0, \ ans = \infty 均无解

The Super Powers
不妨设一个超级幂的唯一分解,对于某质因子pp

pe=ps1s2sme=s1s2sm\begin{aligned} p^e &= p^{s_1s_2\cdots s_m} \\ e &= s_1s_2\cdots s_m \end{aligned}

不难想到,如果一个数是超级幂,满足

{e 是合数,且 e>4枚举底数 x[22641],e64log(2)log(x)1\begin{cases} e \ \text{是合数,且} \ e > 4 \\ \text{枚举底数} \ x \in [2 \to 2^{64}-1], e \leqslant \left\lceil \frac{64 \cdot \log(2)}{\log(x)} \right\rceil - 1 \end{cases}

暴力法即可解决

  • for x[2]\textbf{for} \ \forall x \in [2 \cdots ] 枚举底数x,e64log(2)log(x)1x, \quad e \leqslant \left\lceil \frac{64 \cdot \log(2)}{\log(x)} \right\rceil - 1
    res1for i[1e]res \leftarrow 1 \quad \textbf{for} \ \forall i \in [1 \to e] 枚举指数ii
    resres×x  res=resxi\quad res \leftarrow res \times \prod x \ \Leftrightarrow \ res = res \cdot x^i
    if i 为合数,xi 是 super power, resans{}\textbf{if} \ i \ \text{为合数}, \quad x^{i} \ \text{是 super power}, \ res \to \text{ans}\{\cdots \}
  • 说明,在算法中我们只需要从小到大枚举底数xx,然后取幂指ii 为合数即可,如果xx 可以进行分解
    因为是从小到大枚举的,xx 的因数一定在xx 之前被检查到了,并不会漏解

Teams
根据组合原理,所求的方案是

S(n)=k=1n(nk)(k1)=k=1nk(nk)S(n)=1(n1)+2(n2)+(n1)(nn1)+n(nn)S(n)=n(nn)+(n1)(nn1)+(n2)(nn2)+1(n1)\begin{aligned} S(n) &= \sum_{k=1}^{n} \binom{n}{k} \binom{k}{1} = \sum_{k=1}^{n} k \cdot \binom{n}{k} \\ S(n) &= 1\binom{n}{1} + 2\binom{n}{2} + \cdots (n-1) \binom{n}{n-1} + n \binom{n}{n} \\ S(n) = n\binom{n}{n} + &(n-1)\binom{n}{n-1} + (n-2)\binom{n}{n-2} \cdots + 1\binom{n}{1} \end{aligned}

从而可以推出

2S(n)=n2nS(n)=n2n12S(n) = n \cdot 2^{n} \Rightarrow S(n) = n \cdot 2^{n-1}

唯一分解定理

LCM Cardinality
其实条件可以写成

{ab=ngcd(a,b)gcd(a,b)n\begin{cases} &a \cdot b = n \cdot \text{gcd}(a, b) \\ &\text{gcd}(a, b) \mid n \end{cases}

很容易想到应该对nn 进行素因子分解

  • nn 进行素因子分解

    n=p1s1p2s2pmsma=p1a1p2a2pmsmb=p1b1p2b2pmsm\begin{aligned} n &= p_1^{s_1}p_2^{s_2} \cdots p_m^{s_m} \\ a &= p_1^{a_1}p_2^{a_2} \cdots p_m^{s_m} \\ b &= p_1^{b_1}p_2^{b_2} \cdots p_m^{s_m} \end{aligned}

  • 原问题等价于

    {max(ai,bi)=sisi中有多少种无序(ai,bi)组合\begin{cases} \max(a_i, b_i) = s_i \\ s_i \text{中有多少种无序} (a_i, b_i) 组合 \end{cases}

  • 先从(ai,bi)(a_i, b_i) 中任选一个令其等于sis_i,有(21)2 \choose 1
    剩下的元素从[0,si1][0, s_i-1] 中选,有sis_i 种,一共有(21)si=2si\binom{2}{1} \cdot s_i = 2s_i
    另外考虑到ai=bi=sia_i = b_i = s_i 这一种情况,因为是(ai,bi)(a_i, b_i) 无序数组,所以(si,si)(s_i, s_i) 算作11
     pi\forall \ p_i,一共有2si+12s_i + 1 种选择
  • i(2si+1)2\frac{\prod_i (2s_i + 1)}{2}

    但注意(2si+1)\prod(2s_i + 1) 是奇数,此时(2si+1)\prod(2s_i+1) 的结果中包含(n,n)(n, n) 这一组
    +1+1 后除以22 才是答案

    ans=i(2si+1)+12=i(2si+1)2+1ans = \left\lceil \frac{\prod_i (2s_i + 1) + 1}{2} \right\rceil = \left\lfloor \frac{\prod_i (2s_i+1)}{2} \right\rfloor + 1

UVA10791

  • 先对n=LCMn=\textbf{LCM} 进行素因子分解,n=pisin = \prod p_i^{s_i}
    那么minsum=pisi\min \text{sum} = \sum p_i^{s_i},其实不难证明
    对于任意两个素因子pi,pj,pi<pjp_i, p_j, \quad p_i < p_j,显然有pipjpi+pjp_ip_j \leqslant p_i + p_j

    pipjpi+pjpi+pjpipj11pi+1pj1p_ip_j \leqslant p_i + p_j \Rightarrow \frac{p_i+p_j}{p_ip_j} \leqslant 1 \Rightarrow \frac{1}{p_i} + \frac{1}{p_j} \leqslant 1

    由此pisi\sum p_i^{s_i} 即为最小
  • 在素因子分解后,如果少了某个素因子pip_i,那么lcm\text{lcm}<n< n 了,如果多了某个素因子pip_i,如果此时lcm(A,B)=n\text{lcm}(A, B) = n
    BB/piB \leftarrow B/p_i,仍然满足lcm=n\text{lcm} = n 并且A+BA+B 更小
  • 另外,如果nn 是素数或者是n=1n=1,直接返回n+1n+1 即可

同余与剩余类

任意整数amodpa \bmod p,可以根据余数组成pp 个类,分别为

{0},{1},,{p1}\{0\}, \{1\}, \cdots , \{p-1\}

于是很多同余问题就转换成剩余类计数问题,比如我们可以用s{0}s_{\{0\}} 表示剩余类{0}\{0\} 的个数
剩余类的个数表示为

s{0},s{1},,s{p1}s_{\{0\}}, s_{\{1\}}, \cdots , s_{\{p-1\}}

如果一个BB 位数能够被pp 整除,那么这个数每个数位的和i\sum_{i} 也能够被pp 整除
可以遍历每个数位for i[0,B)\textbf{for} \ \forall i \in [0, B),统计出

s{0},s{1},,s{p1}i1s{1}+2s{2}++(p1)s{p1}(modp)\begin{gathered} s_{\{0\}}, s_{\{1\}}, \cdots , s_{\{p-1\}} \\ \sum_{i} \equiv 1s_{\{1\}} + 2s_{\{2\}} + \cdots + (p-1)s_{\{p-1\}} (\bmod p) \end{gathered}

UVA11489

  • 对于数位bib_i,统计出剩余类个数s{0},s{1},s{2}s_{\{0\}}, s_{\{1\}}, s_{\{2\}},并且计算出

    i(s{1}+2s{2})(mod3)\sum_{i} \equiv (s_{\{1\}} + 2s_{\{2\}}) (\bmod 3)

  • 如果i0(mod3)\sum_{i} \equiv 0 (\bmod 3),那么只需要考虑{0}\{0\} 这个剩余类
    s{0}mod2=1s_{\{0\}} \bmod 2 = 1SS 获胜,否则TT 获胜
  • 如果i{1} or {2}\sum_i \equiv \{1\} \ \textbf{or} \ \{2\},需要考虑{1},{2}\{1\}, \{2\} 这两个剩余类
    • 如果i{1},s{1}>0\sum_i \equiv \{1\}, \quad s_{\{1\}} > 0,要满足取完数,所有数位的和能够被33 整除
      SS 第一次取一定是拿走bi1(mod3)b_i \equiv 1(\bmod 3) 的那个数位,这样
      (11)(mod3)0(mod3)\sum \leftarrow (1-1) (\bmod 3) \Rightarrow \sum \equiv 0 (\bmod 3),才能使剩下的数合法
    • i{2}\sum_i \equiv \{2\} 同理
    • 如果im(mod3),s{m}=0\sum_i \equiv m (\bmod 3), \quad s_{\{m\}} = 0,那么SS 不能取数,TT 获胜
      否则的话,SS 取数之后,转为第一种情况0(mod3)\sum \equiv 0(\bmod 3),只不过最先取数的是TT
      将第一种情况结果取反,就是答案
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
int s[4];
string str;

void solve() {
for (auto x : str) s[x % 3]++;
int mo = 0;
for (int i = 0; i <= 2; i++) mo += i * s[i];
mo %= 3;

if (mo == 0) {
string res;
s[0] % 2 ? res = "S" : res = "T";
printf("%s\n", res.c_str());
}
else {
if (s[mo] == 0) printf("T\n");
else {
string res;
s[0] % 2 ? res = "T" : res = "S";
printf("%s\n", res.c_str());
}
}
}

int main() {
freopen("input.txt", "r", stdin);
int T;
cin >> T;
int kase = 0;
while (T--) {
printf("Case %d: ", ++kase);
memset(s, 0, sizeof s);
cin >> str;
solve();
}
}

组合计数基础

重复元素的全排列方案数

定理nn 个元素,分为mm 组,其中本组元素全部相同,不同组元素不同,并且第ii 组有pip_i
总的排列数为

n!k=1mpk!\frac{n!}{\prod_{k=1}^{m} p_k !}

UVA11076-01
Add Again

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
const int maxn = 15;
const ll one[13] = {
0,
1,
11,
111,
1111,
11111,
111111,
1111111,
11111111,
111111111,
1111111111,
11111111111,
111111111111
};

int n;
ll fac[maxn];
int cnt[maxn];

void prework() {
fac[0] = fac[1] = 1;
for (int i = 2; i <= 12; i++) {
fac[i] = fac[i-1] * (ll)i;
}
}

int main() {
freopen("input.txt", "r", stdin);
prework();

while (scanf("%d", &n) == 1 && n) {
memset(cnt, 0, sizeof cnt);
int sum = 0;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
sum += x, cnt[x]++;
}
ll res = (ll)sum * fac[n-1];
for (int i = 0; i <= 9; i++) res /= fac[cnt[i]];
printf("%lld\n", res * one[n]);
}
}

回文串计数举例

UVA12050
UVA12050-01
UVA12050-02
UVA12050-03

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
const int N = 20;
ll cnt[N];
int C;

void prework() {
cnt[1] = 9, cnt[2] = 9;
for (int i = 3; i < N; i++) {
if (i & 1) cnt[i] = cnt[i-2] * 10;
else cnt[i] = cnt[i-1];
}
}

void solve() {
// i len, C th
int i = 1;
for (; i < N; i++) {
if (cnt[i] < C) C -= cnt[i];
else break;
}
C--;
string str(i, '0');
int k = i/2;
while (C) {
str[k++] = '0' + C % 10;
C /= 10;
}
str[i-1]++;
for (int j = 0; j < i/2; j++) {
str[j] = str[i-1-j];
}
printf("%s\n", str.c_str());
}

int main() {
freopen("input.txt", "r", stdin);
prework();
// for (int i = 1; i < N; i++) debug(cnt[i]);
while (scanf("%d", &C) == 1 && C) {
solve();
}
}