Problem 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(N <= 15 , M <= 100000000)。

Output

可以完成任務的卡片數。

Sample Input

2 4

Sample Output

12

思路：

設卡片號為 a1,a2,...,an,m，跳蚤跳到對應號的次數是 x1,x2,...,xn，跳 m 個單位長度的次數是 xn+1

那么問題就轉化為求：a[1]*x1+a[2]*x2+...+a[n]*xn+m*x(n+1)=1，一共有多少種情況

而上述公式實質是求：GCD(a1,a2,...,an,m)=1

故先對 m 進行素因子分解，求出總的排列組合個數，即有：m^n 種，再根據容斥定理排除公因子非 1 的情況即可

設 g 為公因子非 1 的情況數，f(i) 表示有 i 個公因子的情況數，根據奇加偶減，有：g=f(1)-f(2)+f(3)-...f(k)

如代碼所示：

設g為公因子非1的情況數，f(i) 表示有 i 個公因子的情況數，由容斥原理得：g = f(1) - f(2) + f(3) -... f(k)

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 2000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;LL n,m; LL factor[N]; LL sum[N]; LL num,cnt; void Get_Factor() { //分解質因子num=0;LL temp=m;for(LL i=2; i*i<=temp; i++) {if(temp%i==0) {factor[num++]=i;while(temp%i==0)temp=temp/i;}}if(temp!=1)factor[num++]=temp; }LL quick_pow(LL a,LL b) {LL r=1,base=a;while(b) {if(b&1)r*=base;base*=base;b>>=1;}return r; }LL dfs(LL a,LL b,LL c) {//dfs得到卡片中n+1個數有c的公因子時的方法數if(b==c) {LL temp=m;for(LL i=0; i<c; i++)temp/=sum[i];//表示[1,x]中有多少個數是倍數cnt+=quick_pow(temp,n);//選n個數，每個數x種選擇} else {for(LL i=a; i<num; i++) {sum[b]=factor[i];dfs(i+1,b+1,c);}} }int main() {while(scanf("%lld%lld",&n,&m)!=EOF&&(n+m)) {Get_Factor();LL res=quick_pow(m,n);//m^nfor(LL i=1; i<=num; i++) {cnt=0;dfs(0,0,i);if(i%2)//奇加偶減res-=cnt;elseres+=cnt;}printf("%lld\n",res);}return 0; }

?

總結

以上是生活随笔為你收集整理的跳蚤（POJ-1091）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。