[原创]LightOJ 1090 Trailing Zeroes (II) [分解]【数论】

2016-07-03 16:45:29 Tabris_ 阅读数：369

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

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

题目链接 ：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=120197#problem/Y

Trailing Zeroes (II)
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Submit Status Practice LightOJ 1090

Description

Find the number of trailing zeroes for the following function:

***C(n,r) x p^q ***

where n, r, p, q are given. For example, if n = 10, r = 4, p = 1, q = 1, then the number is 210 so, number of trailing zeroes is 1.

Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains four integers: n, r, p, q (1 ≤ n, r, p, q ≤ 106, r ≤ n).

Output
For each test case, print the case number and the number of trailing zeroes.

Sample Input
2
10 4 1 1
100 5 40 5
Sample Output
Case 1: 1
Case 2: 6

题目大意 ： 就是求***C(n,r) x p^q *** 末尾有几个 0

题解 : 求末尾有几个0 就将其展开成(2^n) * (5^m) * k 然后输出min（n，m） 即可。。

但是数据量特别大 所以需要先预处理

用 five[N],two[N]出 N！中n，m的值(值的含义如上所述) 然后 稍加操作即可求出C(n,m)中n,m的值 (这里并不难,看代码就明白了)

剩下的p^q 就更好办了 p=(2^n) * (5^m) * k
求出的n，m的值在乘上q

最后加上C(n,m)中n,m的值 就是方程里n,m的值

总复杂度 O（1e6*（log（2,1e6）+log（5,1e6））+T *（log（2,p）+log（5,p）））

附本题代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <limits.h>
# include <malloc.h>
# include <ctype.h>
# include <math.h>
# include <string>
# include <iostream>
# include <algorithm>
# include <map>
# include <vector>
# include <set>

using namespace std;

# define LL long long int
# define uLL unsigned long long int
# define _LL __int64

struct Num
{
    int five,two;
};

Num Search( int n)
{
    Num a;
    a.five=a.two=0;
    while(n%2==0)
    {
        n/=2;
        a.two++;
    }
    while(n%5==0)
    {
        n/=5;
        a.five++;
    }
    return a ;
}

Num num[1010101];

Num add(Num a,Num b)
{
    Num tem;
    tem.five=a.five+b.five;
    tem.two =a.two +b.two;
    return tem;
}

Num jian(Num a,Num b)
{
    Num tem;
    tem.five=a.five-b.five;
    tem.two =a.two -b.two;
    return tem;
}

void init()
{
    memset(num,0,sizeof(num));

    for(int i=2;i<=1e6;i++)
    {
        num[i]=add(num[i-1],Search(i));
    }
    return ;
}

int solve(Num a)
{
    return min(a.five,a.two);
}

int main()
{

    init();


    LL t,pp=0;
    scanf("%llu",&t);
    while(t--)
    {
        int n,p,q,r;
        scanf("%d%d%d%d",&n,&r,&p,&q);

        Num m;
        m=Search(p);
        m.five*=q,m.two*=q;

        Num sum = add(jian(jian(num[n] ,num[n-r] ) ,num[r] ), m);


        printf("Case %llu: %d\n",++pp,solve(sum));
    }
    return 0;

}