跳蚤
题目描述
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}$
输入输出样例
2 4
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 ;
}