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

时间:2023-12-05 10:39:44

  题目传送门

跳蚤

题目描述

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<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; typedef long long ll;
const int N=1e6+;
ll n,m,ans,tot,q[N],g[N],top,lim,cnt; void ready(ll ka)
{
for(ll i=; i*i<=ka; ++i) {
if( ka%i== ) {
q[++top]=i;
while( ka%i== ) ka/=i;
}
}
if( ka> ) q[++top]=ka;
} inline ll power(ll x,ll y)
{
ll ret=;
while( y ) {
if( y& ) ret*=x;
y>>=; x*=x;
}
return ret;
} void dfs(ll now,ll hl,ll choose)
{
if( now>top+ ) return;
if( choose==lim ) {
g[++cnt]=hl; return;
}
dfs(now+,hl*q[now],choose+);
dfs(now+,hl,choose);
} int main()
{
cin>>n>>m;
ready(m);
ans=power(m,n);
for(ll i=; i<=top; ++i) {
lim=i; cnt=;
dfs(,,);
if( i& )
for(ll j=; j<=cnt; ++j) ans-=power(m/g[j],n);
else
for(ll j=; j<=cnt; ++j) ans+=power(m/g[j],n);
}
cout<<ans<<'\n';
return ;
}