萌新集中营第四期——数学小知识

题解

题目链接：https://vjudge.net/contest/154954

A - Eddy's AC难题

题目大意

从 n 个人中选择一部分人(或者全部)分成两组进行比较 ac 的数量，要求使第一组中的最小 ac 数大于第二组中的最大 ac 数,求出情况数，假设摘录下的人数为 n 人，而且每个人 ac 的数量不会相等，最后结果在64位整数范围内

Input

包含多组数据，每组包含一个整数 n

Output

输出符合要求的总的方案数，每个输出占一行

Sample Input

2
4

Sample Output

1
17

解题思路

**组合数**
    插板法，用插板来分组，answer = 1*C(2, n) + 2*C(3, n) + …… + (n-1)*C(n, n)，从 n 个人中依次抽取2，3，……，n个人，插板的位置依次有1,2，……，n-1种情况

代码

#include <cstdio>
#define ll long long int
ll Combination(ll n, ll m);
int main()
{
    ll n;
    while(scanf("%lld", &n)!=EOF)
    {
        ll ans = 0, i;
        for(i=2;i<=n;i++)
        {
            ans = ans + (i-1)*Combination(n, i);
        }
        printf("%lld\n", ans);
    }
    return 0;
}
ll Combination(ll n, ll m)
{
    ll i, j, c = 1;
    for(i=n, j=1;i>n-m;i--,j++)
    {
        c = c * i / j;
    }
    return c;
}

该题收获

1. 刚开始混淆了组合数和排列数，本题需要利用插板分割和组合数

B - RPG的错排

题目大意

将 n 个人和她们的名字一一对应，要求答对一半或以上才算过关，请问有多少组情况能顺利过关

Input

多个 case ,每个 case 包括一个 n （n<=25）, 当 n = 0 时输入结束

Output

输出情况数，每个输出占一行

Sample Input

1
2
0

Sample Output

1
1

解题思路

**错排**
    将错排和组合数相结合， n 个人中取二分之一，D(0)*C(n,n-0)+D(1)*C(n,n-1)+……+D(n/2)*C(n,n-n/2)即为所求结果

代码

#include <cstdio>
#define e 2.718281828459
typedef long long int ll;
ll Combination(ll n, ll m);
int main()
{
    ll n;
    while(scanf("%lld", &n)&&n!=0)
    {
        ll i, j, ans=1, d;
        for(i=1;i<=n/2;i++)
        {
            for(j=1,d=1;j<=i;j++)
            {
                d = d * j;
            }
            ans = ans + (long long int)((long double)d/e+0.5) * Combination(n, n-i);
        }
        printf("%lld\n", ans);
    }
    return 0;
}
ll Combination(ll n, ll m)
{
    ll i, j, c = 1;
    for(i=n, j=1;i>n-m;i--,j++)
    {
        c = c * i / j;
    }
    return c;
}

该题收获

1. 错排公式：D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!]
   简化后的公式：D(n) = [n!/e+0.5]   (e = 2.718281828459，这里[x]为x的整数部分)
2. 错排公式可由递归或容斥原理推导而来，理解了两种来源方式
   递归公式：D(n) = (n-1) [D(n-2) + D(n-1)]
3. 除了应用在结构体上， typedef 的使用，效果与 #define 相似

G - The Euler function

题目大意

欧拉函数 euler(n) 是指在 [1, n) 中与 n 互质的数的个数，求出 [euler(a), euler(b)] 的总和

Input

包含多组用例，每行有两个整数 a ， b (2

Output

输出 euler(a) + euler(a+1) + …… + euler(b) 的结果

Sample Input

3 100

Sample Output

3042

解题思路

**欧拉函数**
    当数据过大，直接求解会超时，需要用筛选法打表

代码

#include <cstdio>
#define Max 3000001
typedef long long int LL;
void Init();
LL euler[Max];
int main()
{
    LL a, b, ans, i;
    Init();
    while(scanf("%lld %lld", &a, &b)!=EOF)
    {
        ans = 0;
        for(i=a;i<=b;i++)
        {
            ans = ans + euler[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}
void Init()
{
     euler[1]=1;
     for(int i=2;i<Max;i++)
       euler[i]=i;
     for(int i=2;i<Max;i++)
        if(euler[i]==i)
           for(int j=i;j<Max;j+=i)
              euler[j]=euler[j]/i*(i-1);
}

该题收获

1. 定义的数组长度不能过大，会编译错误，或者超出内存
2. 求欧拉函数有两种办法，注意当数据过大时直接求解会超时，需要筛选法打欧拉函数表
3. 理解了欧拉函数直接求解的方式
4. 先进行除法防止中间数据溢出
5. euler(1) = 1
6. 欧拉公式的延伸：一个数的所有质因子之和是euler(n)*n/2

@欧拉函数模板

//直接求解欧拉函数
int euler(int n)
{
     int res=n,a=n;  
     for(int i=2;i*i<=a;i++)
     {  
         if(a%i==0)
         {  
             res=res/i*(i-1);   
             while(a%i==0) a/=i;  
         }  
     }  
     if(a>1) res=res/a*(a-1);  
     return res;  
} 
//筛选法打欧拉函数表   
#define Max 1000001
int euler[Max];
void Init()
{   
     euler[1]=1;  
     for(int i=2;i<Max;i++)  
       euler[i]=i;  
     for(int i=2;i<Max;i++)  
        if(euler[i]==i)  
           for(int j=i;j<Max;j+=i)  
              euler[j]=euler[j]/i*(i-1);
}