BZOJ1220 HNOI2002 跳蚤【容斥原理+高精度】*

BZOJ1220 HNOI2002 跳蚤

Description

Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。当确定N和M后，显然一共有MN张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。

Input

输入文件有且仅有一行，包括用空格分开的两个整数N和M。

Output

输出文件有且仅有一行，即可以完成任务的卡片数。 $1≤M≤10^8，1≤N≤M$ 且 $M^N≤10^{16}$ 。（注意：这个数据范围是错的，此题需要高精度。）

Sample Input

2 4

Sample Output

HINT

此题需要高精度！

我们考虑有解的情况是什么
就是对于所有的的gcd和m互质
直接统计不好搞，就可以用容斥的思想
考虑所有解减去不合法的解
那么如何考虑减去不合法解呢?
考虑容斥一下，累加最大公约数是i的方案数
然后对于i的容斥系数是 $(−1)^i的质因子数$
所以对于每个i的贡献是 $((m/i)^n*(−1)i的质因子数)$
前面一部分的意思是每个位置都可以选择i的倍数的方案数，这也是容斥系数的根源所在
for example：

一共有三个质因子
我们考虑60的贡献
在减去了贡献
在加上了贡献
所以在60处贡献减去（因为考虑的是减去不合法方案）
然后看10的贡献
在减去了贡献
所以在10加上贡献
就很显然了

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 1010
  4 #define LL long long
  5 #define fu(a,b,c) for(int a=b;a<=c;++a)
  6 #define fd(a,b,c) for(int a=b;a>=c;--a)
  7 const int Base=10000;
  8 struct Big{
  9   int len,w,t[N];
 10   Big(){len=w=1;memset(t,0,sizeof(t));}
 11 }ans;
 12 Big change(int a){
 13   Big c;c.len=0;
 14   if(a<0)c.w=-1;
 15   a=abs(a);
 16   while(a)c.t[++c.len]=a%Base,a/=Base;
 17   return c;
 18 }
 19 void print(Big c){
 20   if(c.w==-1)printf("-");
 21   printf("%d",c.t[c.len]);
 22   fd(i,c.len-1,1)printf("%04d",c.t[i]);
 23   printf("
");
 24 }
 25 bool unsigned_cmp(Big a,Big b){//只比较数字大小
 26   if(a.len>b.len)return 1;
 27   if(a.len<b.len)return 0;
 28   fd(i,a.len,1){
 29     if(a.t[i]>b.t[i])return 1;
 30     if(a.t[i]<b.t[i])return 0;
 31   }
 32   return 1;
 33 }
 34 Big unsigned_add(Big a,Big b){
 35   Big c;c.len=max(a.len,b.len);
 36   fu(i,1,c.len)c.t[i]=a.t[i]+b.t[i];
 37   fu(i,1,c.len){
 38     if(c.t[i]>Base){
 39       c.t[i]-=Base;
 40       c.t[i+1]++;
 41       if(i==c.len)c.len++;
 42     }
 43   }
 44   return c;
 45 }
 46 Big unsigned_sub(Big a,Big b){
 47   Big c;c.len=max(a.len,b.len);
 48   fu(i,1,c.len)c.t[i]=a.t[i]-b.t[i];
 49   fu(i,1,c.len){
 50     if(c.t[i]<0){
 51       c.t[i]+=Base;
 52       c.t[i+1]--;
 53     }
 54   }
 55   fd(i,c.len,1){
 56     if(!c.t[i])c.len--;
 57     else break;
 58   }
 59   return c;
 60 }
 61 Big add(Big a,Big b){
 62   Big c;
 63   if(unsigned_cmp(b,a))swap(a,b);
 64   if(a.w==1&&b.w==1)c=unsigned_add(a,b),c.w=1;
 65   if(a.w==1&&b.w==-1)c=unsigned_sub(a,b),c.w=1;
 66   if(a.w==-1&&b.w==1)c=unsigned_sub(a,b),c.w=-1;
 67   if(a.w==-1&&b.w==-1)c=unsigned_add(a,b),c.w=-1;
 68   return c;
 69 }
 70 Big sub(Big a,Big b){b.w=0-b.w;return add(a,b);}
 71 Big mul(Big a,Big b){
 72   Big c;c.w=a.w*b.w;
 73   c.len=a.len+b.len-1;
 74   fu(i,1,a.len)
 75     fu(j,1,b.len)
 76       c.t[i+j-1]+=a.t[i]*b.t[j];
 77   fu(i,1,c.len){
 78     if(c.t[i]>Base){
 79       c.t[i+1]+=c.t[i]/Base;
 80       c.t[i]%=Base;
 81       if(i==c.len)c.len++;
 82     }
 83   }
 84   return c;
 85 }
 86 Big fast_pow(Big a,int b){
 87   Big ans;ans.t[1]=1;
 88   if((b&1)&&a.w==-1)ans.w=-1;
 89   while(b){
 90     if(b&1)ans=mul(ans,a);
 91     b>>=1;
 92     a=mul(a,a);
 93   }
 94   return ans;
 95 }
 96 int n,m;
 97 int p[N],cnt=0;
 98 bool check(int vl){
 99   fu(i,2,sqrt(vl))
100     if(vl%i==0)return 0;
101   return 1;
102 }
103 void divide(int num){
104   fu(i,2,num){
105     if(num%i==0&&check(i)){
106       p[++cnt]=i;
107       while(num%i==0)num/=i;
108     }
109   }
110 }
111 void dfs(int tmp,LL sum,int typ){
112   if(tmp>cnt)return;
113   dfs(tmp+1,sum,typ);
114   sum*=p[tmp];typ*=-1;
115   Big now=change(sum);
116   now=fast_pow(change(m/sum),n);
117   now.w=typ;
118   ans=add(ans,now);
119   dfs(tmp+1,sum,typ);
120 }
121 int main(){
122   scanf("%d%d",&n,&m);
123   divide(m);
124   ans=fast_pow(change(m),n);
125   dfs(1,1ll,1);
126   print(ans);
127   return 0;
128 }