题目描述
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张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。
题目大意是给定两个整数n和m，求出长度为n+1满足条件的数列data的个数，数列的要求下： 1）1<=data[i]<=m,for1<=i<=n 2)data[n+1]=m; 3）这个n+1个数满足：存在x1,x2,…,xn,xn+1,满足x1data[1]+x2data[2]+…+x(n+1)*data[n+1]=1； 根据数论的知识，若存在这样的x1,x2…xn+1,则data[1],data[2]…data[n+1]的最大公约数为1
具体解题步骤如下： 1、求出满m的所有质因子,存入数组num 2、求出总的序列个数吗m^n 3、设t(k)表示数列最大公约数为（k个质因子乘积）的数列的个数
f=mn-t(1)+t(2)-t(3)+…(-1)k*t(k); 答案 = (m n) - （有公因数2的n元组）- （有公因数3的n元组）- （有公因数5的n元组）+ （有公因数2，3的n元组） +（有公因数2，5的n元组） + （有公因数3，5的n元组）- （有公因数2，3，5的n元组）。这个比公式形象些 有公因数d的n元组，每个位置上有 (m/d)个选择（1 ~ m里面有m/d个d的倍数），根据乘法原理，可以得出有公因数d的n元组有 (m/d)n 个。
Code:
#include<bits/stdc++.h> using namespace std; #define int unsigned long long const int N=1e4+10; int n,m,tot,a[N],ans,b[N],sum,M; int cal(int x) { int s=x; for(int i=2;i<=n;i++) x=x*s; return x; } void Get(int st,int num,int al) { if(num==al+1) { int t=1; for(int i=1;i<=al;i++) t*=b[i]; sum+=cal(M/t); } else { for(int i=st;i<=tot;i++) { b[num]=a[i]; Get(i+1,num+1,al); } } } signed main() { cin>>n>>m; M=m; ans=cal(m); for(int i=2;i*i<=m;i++) { if(m%i!=0) continue; a[++tot]=i; while((m%i)==0) m/=i; } if(m!=1&&m>0) a[++tot]=m; for(int i=1;i<=tot;i++) { sum=0;Get(1,1,i); if(i%2==1) ans-=sum; else ans+=sum; } cout<<ans; return 0; }