nefu 119 组合素数

    xiaoxiao2021-12-15  23

    组合素数 Problem:119 Time Limit:1000ms Memory Limit:65536K Description 小明的爸爸从外面旅游回来给她带来了一个礼物,小明高兴地跑回自己的房间,拆开一看是一个很大棋盘(非常大),小明有所失望。不过没过几天发现了大棋盘的好玩之处。从起点(00)走到终点(n,n)的非降路径数是C(2n,n),现在小明随机取出1个素数p, 他想知道C(2n,n)恰好被p整除多少次?小明想了很长时间都没想出来,现在想请你帮助小明解决这个问题,对于你来说应该不难吧! Input 有多组测试数据。 第一行是一个正整数T,表示测试数据的组数。接下来每组2个数分别是n和p的值,这里1<=n,p<=1000000000。 Output 对于每组测试数据,输出一行,给出C(2n,n)被素数p整除的次数,当整除不了的时候,次数为0。 Sample Input 2 2 2 2 3 Sample Output 1 1

    从(0,0)出发到(n,n) 一共要向下移动n步 向右移动n步 一共移动2n步 2n步中选择n步向下走 其余n步向右走 所以一共有C(2n,n)种情况


    不难发现C(2n,n)里 2n!能约去2个n!的因子 所以求出2n!包含的p的因子数 - 2*(n!包含的p的因子数)就是答案


    #include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 #define pll pair<ll,ll> #define pid pair<int,double> ll slove(ll n,ll p){ ll ans=0,divi=p; while(divi<=n){ ans+=n/divi; divi*=p; } return ans; } int main() { //freopen("/home/lu/文档/r.txt","r",stdin); //freopen("/home/lu/文档/w.txt","w",stdout); int T; ll n,p; scanf("%d",&T); while(T--){ scanf("%lld%lld",&n,&p); printf("%lld\n",slove(2*n,p)-2*slove(n,p)); } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-1000138.html

    最新回复(0)