首页 > 代码库 > POJ 3146 & HDU 3304 Interesting Yang Yui Triangle(杨辉三角)

POJ 3146 & HDU 3304 Interesting Yang Yui Triangle(杨辉三角)

2024-07-24 10:02:12   217人阅读

题目链接：

HDU 3304 :http://acm.hdu.edu.cn/showproblem.php?pid=3304

POJ 3146  :http://poj.org/problem?id=3146


Problem Description
Harry is a Junior middle student. He is very interested in the story told by his mathematics teacher about the Yang Hui triangle in the class yesterday. After class he wrote the following numbers to show the triangle our ancestor studied.


1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
......


He found many interesting things in the above triangle. It is symmetrical, and the first and the last numbers on each line is 1; there are exactly i numbers on the line i.

Then Harry studied the elements on every line deeply. Of course, his study is comprehensive.

Now he wanted to count the number of elements which are the multiple of 3 on each line. He found that the numbers of elements which are the multiple of 3 on line 2, 3, 4, 5, 6, 7, ... are 0, 0, 2, 1, 0, 4, ... So the numbers of elements which are not divided by 3 are 2, 3, 2, 4, 6, 3, ... , respectively. But he also found that it was not an easy job to do so with the number of lines increasing. Furthermore, he is not satisfied with the research on the numbers divided only by 3. So he asked you, an erudite expert, to offer him help. Your kind help would be highly appreciated by him.

Since the result may be very large and rather difficult to compute, you only need to tell Harry the last four digits of the result.
 
Input
There are multiple test cases in the input file. Each test case contains two numbers P and N , (P < 1000, N<=10^9) , where P is a prime number and N is a positive decimal integer.

P = 0, N = 0 indicates the end of input file and should not be processed by your program.
 
Output
For each test case, output the last four digits of the number of elements on the N + 1 line on Yang Hui Triangle which can not be divided by P in the format as indicated in the sample output.
 
Sample Input
3 4 
3 48 
0 0
 
Sample Output
Case 1: 0004
Case 2: 0012
 
Source
2006 Asia Regional Shanghai

题意：

求出杨辉三角的N+1行的数中不能被P整除的数的个数！


思路：

首先杨辉三角是对称的，

它的N+1行的每一位数分别是：C(n，0)，C(n，1)…………C(n，n)！

 n! 所包含的 p 的幂: f(n,p) = n/p+n/(p^2)+n/(p^3)+...

C(n,m) = n!/(m!(n-m)!)，判断这个数能否被 p 整除也就是看它是否含有因子p，

n!中含有n/p+n/p^2+....n/p^k个p，

又C(n,m)是整数，所以不能被p整除的情况应该是：n!中含p的个数等于其分子m！和 (n-m)!所含有p因子的个数和。

即需要满足：n/(p^i) = k/(p^i) + (n-k)/(p^i)，

实际上可以枚举第i位的表示，即0,1,2,3...a。

每一位都满足，最后答案就是(a1+1)*(a2+1)...(ak+1)；


具体请戳：http://blog.163.com/scaulyd@126/blog/static/15522639520103124641416/


代码如下：

//#pragma warning (disable:4786)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <climits>
#include <ctype.h>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <deque>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-9;
//const double pi = atan(1.0)*4;
const double pi = 3.1415926535897932384626;
#define INF 1e18
//typedef long long LL;
//typedef __int64 LL;
int main()
{
    int P, N;
    int cas = 0;
    while(~scanf("%d%d",&P,&N))
    {
        if(P==0 && N==0)
            break;
        int sum = 1;
        for(int i = N; i > 0; i/=P)
        {
            sum*=i%P+1;
        }

        printf("Case %d: %04d\n",++cas,sum%10000);
    }
}



POJ 3146 & HDU 3304 Interesting Yang Yui Triangle(杨辉三角)


联系
我们