[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 C: 勤劳的ACgirls

2017-06-03 01:51:32 Tabris_ 阅读数：575

博客爬取于2020-06-14 22:40:21
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849551

题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=2
——————————————————————————————————————————
g输出请用%lld 参赛请加qq群160384471获取最新消息
Problem C: 勤劳的ACgirls
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 100 Solved: 39
[Submit][Status][Web Board]
Description
zjc的ACgirls队的队员最近比较忙，为了能够取得更好的比赛成绩，他们制定了一个m天a掉n题的计划，a掉一题可以是这m天的任何时候。
为了表示对acmer事业的热爱，队长wc要求每天必须至少要ac掉k题，这m天每天ac掉的题数可以用一个m元组表示。
设不同的m元组一共有c个，请问c的末尾有多少个0？（如果c是0，输出0）
Input
多组测试数据，处理到文件结束。（测试例数量<=160000）

输入的每一行是一个测试例，分别是m、n和k（0<=m,n,k<=1e9），含义如前所述。

Output
每组测试例中m元组的数量的末尾0的个数，占一行。
Sample Input
3 11 0
3 11 1
999 99999 4
Sample Output
0
0
5
——————————————————————————————————————————

就是将n-m*k个题放到m天做，

就是简单的组合么,

在n+m-1个东西选m-1个 (-1的意思是挡板，将n个题分成m天)

结果就是

n=n−m∗kC(n+m−1,m−1)=(n+m−1)!(n)!×(m−1)!n=n-m*k \\C(n+m-1,m-1)=\dfrac{(n+m-1)!}{(n)!\times (m-1)!}

分别计算(n+m−1)!   ,(n)!   ,(m−1)!(n+m-1)!\ \ \ ,(n)!\ \ \ ,(m-1)!中2,5的个数就好了

附本题代码
——————————————————————————————————————————

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
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

LL solve(LL x,int y){
    LL sum = 0;
    while(x){
        x/=y;
        sum+=x;
    }
    return sum;
}

LL n,m,k;
int main(){
    while(~scanf("%lld%lld%lld",&m,&n,&k)){
        n=n-m*k;
        if(n<=0) puts("0");
        else{
            LL sum =solve(n+m-1,5)-solve(n,5)-solve(m-1,5);
            LL sum2=solve(n+m-1,2)-solve(n,2)-solve(m-1,2);
            sum=min(sum,sum2);
            sum=max(0ll,sum);
            printf("%lld\n",sum);
        }
    }
    return 0;
}