题解 - [Ural 1091] Tmutarakan Exams

发表于 更新于 分类于 ， 本文字数： 563 阅读时长 ≈ 2 分钟

题目链接

原始题面

University of New Tmutarakan trains the first-class specialists in mental arithmetic. To enter the University you should master arithmetic perfectly. One of the entrance exams at the Divisibility Department is the following. Examinees are asked to find \(K\) different numbers that have a common divisor greater than \(1\). All numbers in each set should not exceed a given number \(S\). The numbers \(K\) and \(S\) are announced at the beginning of the exam. To exclude copying (the Department is the most prestigious in the town!) each set of numbers is credited only once (to the person who submitted it first)

Last year these numbers were \(K=25\) and \(S=49\) and, unfortunately, nobody passed the exam. Moreover, it was proved later by the best minds of the Department that there do not exist sets of numbers with the required properties. To avoid embarrassment this year, the dean asked for your help. You should find the number of sets of K different numbers, each of the numbers not exceeding \(S\), which have a common divisor greater than \(1\). Of course, the number of such sets equals the maximal possible number of new students of the Department

Input

The input contains numbers \(K\) and \(S\) (\(2 ≤ K ≤ S ≤ 50\))

Output

You should output the maximal possible number of the Department's new students if this number does not exceed \(10000\) which is the maximal capacity of the Department, otherwise you should output \(10000\)

Sample

input output
3 10 11

Problem Author: Stanislav Vasilyev
Problem Source: USU Open Collegiate Programming Contest March'2001 Senior Session

题意简述

给出 \(K\) 和 \(S\), 求在 \([1,S]\) 内互不相同的 \(K\) 个数的最大公约数不为 \(1\) 的数对个数，若大于 \(10000\) 则输出 \(10000\)

解题思路

设 \(\operatorname{num}(K,S,d)\) 为: \([1,S]\) 内互不相同的 \(K\) 个数的最大公约数为 \(d\) 的数对个数

由容斥定理可知，所求应为

\[ \sum_{i\in\{\text{primes}~\text{less}~\text{than}~S\}}\operatorname{num}(K,S,i)-\sum_{i,j\in\{\text{primes}~\text{less}~\text{than}~S\},~i<j}\operatorname{num}(K,S,ij)+... \]

我们很容易就能发现

\[ \operatorname{num}(K,S,d)={\lfloor\frac{S}{d}\rfloor\choose K} \]

所以所求即为

\[ \sum_{i\in\{\text{primes}~\text{less}~\text{than}~S\}}{\lfloor\frac{S}{i}\rfloor\choose K}-\sum_{i,j\in\{\text{primes}~\text{less}~\text{than}~S\},~i<j}{\lfloor\frac{S}{ij}\rfloor\choose K}+... \]

然而，我们注意到 \(S\leqslant 50\), 而且最小的三素数乘积 \(2\times 3\times 5=30\), 所以

\[ \forall i,j,k\in\{\text{prime}\},~\operatorname{num}(K,S,ijk)=0 \]

故所求即为

\[ \sum_{i\in\{\text{primes}~\text{less}~\text{than}~S\}}{\lfloor\frac{S}{i}\rfloor\choose K}-\sum_{i,j\in\{\text{primes}~\text{less}~\text{than}~S\},~i<j}{\lfloor\frac{S}{ij}\rfloor\choose K} \]

代码参考

Show code

URAL_1091view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
const int pri[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
long long c[55][55];
int main() {
  for (int i = 0; i <= 50; ++i) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; ++j) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
  }
  int k, s;
  scanf("%d%d", &k, &s);
  long long ans = 0;
  for (int i = 0; i < sizeof(pri) / sizeof(pri[0]) && s >= pri[i]; ++i)
    ans += c[s / pri[i]][k];
  for (int i = 0; i < sizeof(pri) / sizeof(pri[0]) && s >= pri[i]; ++i)
    for (int j = i + 1;
         j < sizeof(pri) / sizeof(pri[0]) && s >= pri[i] * pri[j];
         ++j)
      ans -= c[s / (pri[i] * pri[j])][k];
  printf("%lld\n", ans > 10000 ? 10000 : ans);
}