洛谷P2231 [HNOI2002]跳蚤 [数论，容斥原理]

题目传送门

跳蚤

题目描述

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后，显然一共有$M^N$张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。

输入输出格式

输入格式：

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

输出格式：

输出文件有且仅有一行，即可以完成任务的卡片数。

$1\leq N\leq M\leq 10^8$且$M^N\leq10^{16}$

输入输出样例

输入样例#1：

2 4

输出样例#1：

12

说明

这12张卡片分别是：

(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4),

(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4)

分析：

大力推结论的数学题。

大部分人好像都是用莫比乌斯函数做的，这里博主用的是大力推结论+容斥原理。

推这道题的过程是真的有点意思，一步一步来：

首先，我们要知道能跳到目标位置的情况是什么。这个用裴蜀定理可以推出，向某一方向可以跳的距离一定是使用了的数字的最大公约数的倍数。那么我们也就知道了，能跳到左边一个单位的情况就是$n+1$个数字中至少有一对互质的数。

但是我们直接求这种情况似乎太难了，不如反过来，用所有情况数减去不能跳到的情况。那么我们就要想，怎么去计算不能跳到的情况。

显然，选的数的最大公约数一定要大于$1$。而且题目又限定了第$n+1$个数字是$m$，那么我们就把所有的$m$的质因数拿来操作。

怎么操作呢？先选取一个质因数，然后把所有$\leq m$的包含这个质因数的数的个数求出，然后用总情况数减去这些数构成的卡片的情况数。

这样貌似就已经可以了，但是博主交上去，$20pts$。。。

为什么？因为会减去重复的情况。这里举个例：$n=2,m=12$，$m$的质因数有$2,3$。其中取$2$操作时有这种情况：$6,6,12$，而取$3$操作时也有这种情况！

所以这里需要用容斥原理把重复情况加回来。

Code：

//It is made by HolseLee on 19th Oct 2018

//Luogu.org P2231

#include

#include

#include

#include

using namespace std;

typedef long long ll;

const int N=1e6+7;

ll n,m,ans,tot,q[N],g[N],top,lim,cnt;

void ready(ll ka)

{

for(ll i=2; i*i<=ka; ++i) {

if( ka%i==0 ) {

q[++top]=i;

while( ka%i==0 ) ka/=i;

}

}

if( ka>1 ) q[++top]=ka;

}

inline ll power(ll x,ll y)

{

ll ret=1;

while( y ) {

if( y&1 ) ret*=x;

y>>=1; x*=x;

}

return ret;

}

void dfs(ll now,ll hl,ll choose)

{

if( now>top+1 ) return;

if( choose==lim ) {

g[++cnt]=hl; return;

}

dfs(now+1,hl*q[now],choose+1);

dfs(now+1,hl,choose);

}

int main()

{

cin>>n>>m;

ready(m);

ans=power(m,n);

for(ll i=1; i<=top; ++i) {

lim=i; cnt=0;

dfs(1,1,0);

if( i&1 )

for(ll j=1; j<=cnt; ++j) ans-=power(m/g[j],n);

else

for(ll j=1; j<=cnt; ++j) ans+=power(m/g[j],n);

}

cout<

return 0;

}