Written with StackEdit.
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)后，显然一共有(M^N)张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。
Input
输入文件有且仅有一行，包括用空格分开的两个整数(N)和(M)。
Output
输出文件有且仅有一行，即可以完成任务的卡片数.(1≤M≤10^8，1≤N≤M，)且(M^N≤10^16.)
Sample Input
2 4
Sample Output
12
Solution
- 显然,根据裴蜀定理,满足(gcd(a_1,a_2,a_3,......a_n,M)=1)的即为一组解.我们要对其进行计数.
- 考虑用所有的方案(M^N)减去(gcd)不为(1)的数.
- 因为最后一个数为(M),所以(gcd)一定是(M)的约数.
- 将(M)分解质因数后,二进制枚举质因数的组合情况.
- 若当前组合出来的数是(prod),那么是(prod)倍数的有(frac{p}{prod})个.
- 那么这样的方案数为((frac{p}{prod})^N.)
- 由于会产生重复计数,所以需要容斥处理.奇数个质因子(+),偶数个(-).
这样看来,(M^N)也是一种特殊情况,(prod=1),个数为(0),所以用加.
#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
int n,m;
LoveLive fpow(LoveLive a,LoveLive b)
{
LoveLive res=1;
while(b)
{
if(b&1)
res*=a;
a*=a;
b>>=1;
}
return res;
}
LoveLive factor[50];
int main()
{
n=read(),m=read();
LoveLive ans=fpow(m,n);
int p=m,siz=0;
for(int i=2;i*i<=p;++i)
if(p%i==0)
{
factor[++siz]=i;
while(p%i==0)
p/=i;
}
if(p>1)
factor[++siz]=p;
LoveLive lim=(1<<siz)-1;//质因数的组合方式,二进制枚举
for(LoveLive i=1;i<=lim;++i)
{
LoveLive prod=1,cnt=0;//乘积与这种方案的质因数个数
for(int j=1;j<=siz;++j)
if((i>>(j-1))&1)
{
prod*=factor[j];
++cnt;
}
if(cnt&1)
ans-=fpow(m/prod,n);
else
ans+=fpow(m/prod,n);
}
printf("%lld
",ans);
return 0;
}