CF369E. ZS and The Birthday Paradox

 1 /*
 2 cf369E. ZS and The Birthday Paradox
 3 http://codeforces.com/contest/711/problem/E
 4 抽屉原理+快速幂+逆元+勒让德定理+费马小定理+欧拉定理+数论
 5 题解：https://amoshyc.github.io/ojsolution-build/cf/cf369/pe.html
 6 
 7 坑点：
 8 1、long long 类型的常量一定要加LL，否则1<<n只在int范围内
 9 2、带模的题目，最后一定要判断是否答案为负，答案为负数要加mod
10 */
11 #include <cstdio>
12 #include <algorithm>
13 using namespace std;
14 const int mod=1000003;
15 long long n,k;
16 long long Legendre(long long n,long long p)//勒让德定理:O(logn) 算出n!中有多少个p
17 {
18     long long ans=0;
19     while(n>0)
20     {
21         ans+=n/p;
22         n/=p;
23     }
24     return ans;
25 }
26 long long pow(long long base,long long n)
27 {
28     long long ans=1;
29     base=base%mod;//先取模防止爆long long
30     while(n>0)
31     {
32         if(n&1)
33             ans=(ans*base)%mod;
34         base=(base*base)%mod;
35         n>>=1;
36     }
37     return ans;
38 }
39 int main()
40 {
41     //freopen("cf711E.in","r",stdin);
42     scanf("%I64d%I64d",&n,&k);
43     if(n<=63 && k>(1LL<<n))//抽屉原理
44     {
45         printf("1 1
");
46         return 0;
47     }
48     long long gcd=Legendre(k-1,2);
49     long long p=1,q;//p/q;
50     q=((n%(mod-1))*((k-1)%(mod-1))-gcd%(mod-1))%(mod-1)+mod-1;//欧拉函数降幂
51     //q=(n%(mod-1))*((k-1)%(mod-1))+mod-1-gcd; this is a wrong way!!!!!!
52     q=pow(2,q)%mod;//q=2^( n(k-1)-gcd ) <=> 2^((n(k-1)-gcd)%phi(mod)+phi(mod) );
53     if(k-1>=mod)//抽屉原理得出在分子中必定存在一个%mod=0，标程大坑，不能直接输出1 1，即此处不约分。
54         p=0;
55     else
56     {
57         long long val=pow(2,n);
58         for(long long i=1;i<=k-1;i++)
59         {
60             p=(p*((val-i))%mod)%mod;
61         }
62         if(gcd)
63         {
64             p=(p*pow(pow(2,gcd),mod-2))%mod;
65             //p=(p+mod)/pow(2,gcd);
66         }
67     }
68     p=q-p;
69     if(p<0)//判断是否为负
70         p+=mod;
71     printf("%I64d %I64d
",p,q);
72     return 0;
73 }