本文主要是介绍poj1091 跳蚤 解不定方程 容斥原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 参考博客：https://blog.csdn.net/yitiaodacaidog/article/details/15462857 跳蚤
Description Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 Input 两个整数N和M(N <= 15 , M <= 100000000)。 Output 可以完成任务的卡片数。 Sample Input Sample Output Hint 这12张卡片分别是： Source HNOI 2001 |
算法分析：
先补充一个原理
1、最大公约数原理
设d = gcd(A1, A2, ..., An)，则必然可以找到或正或负的整数Xi, 使
A1X1 + A2X2 + ... + AnXn = d
.2、A1X1 + A2X2 + ... + AnXn = 1有解的充要条件是d = gcd(A1, A2, ..., An) = 1
所以，我们假设卡片上的标号分别是a1,a2,...,an,M，
跳蚤跳对应标号的卡片的次数分别为x1,x2,...,xn,xn+1，
那么要满足已知条件只需满足方程a1*x1+a2*x2+...+an*xn+M*xn+1=1有解，
即gcd(a1,a2,...,an,m)=1, 但互质情况不好求，所以求不互质情况。
容斥原理解题思路以前写过，这里重申
将M因式分解：M = P1^K1 * P2^K2 + ... + Pr^Kr
则区间[1, M]内的整数是Pi的倍数的有：Pi, 2Pi, 3Pi, ..., r1Pi （这里的r1 = M / Pi）
而同理，是Pi.Pk的倍数有：Pi.Pk, 2Pi.Pk, ..., rPi.Pk （这里的r i= M / Pi.Pk)
当前n个数中都含有P1的因数的情况数有r1^n = (M / P1)^n种（他可以选重复，所以不用担心不够n个），含有P2的因数情况数有r2^n = (M / P2)^n种，……
而总可能数为M^n种，故结果res = M^n - [(M / P1)^n + (M / P2)^n + ... + (M / Pn)^n] + ... + (-1)^(n+1) * [M / (P1*P2*P3*...*Pk)]，
容斥定理推出公式：公因子不为1的个数 f = t(1) - t(2) + t(3) - ... + (-1) ^ (k - 1) t(k)
符合要求个数为 m ^ n – f
代码实现：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
using namespace std;
typedef long long ll;
long long ans=0,sum=0,r;
int n,m;
ll fac[105];
void factor(ll m)
{sum = 0;ll tmp = m;for(ll i = 2; i*i<=tmp; i++) //官方版的唯一分解定理if(tmp%i==0){fac[sum++] = i;while(tmp%i==0) tmp /= i;}if(tmp>1) fac[sum++] = tmp;
}
void dfs(int i,int cnt,int tmp)//i代表数组的下标
{ //cnt代表几个元素的最小公倍数 if(cnt&1) //容斥原理ans+=(ll)pow(m/tmp,n);elseans-=(ll)pow(m/tmp,n);for(int j=i+1;j<sum;j++)dfs(j,cnt+1,tmp*fac[j]);
}int main()
{while(scanf("%d%d",&n,&m)!=EOF){ ans=0;sum=0;factor(m);for(int i=0;i<sum;i++)dfs(i,1,fac[i]);ans=pow(m,n)-ans;printf("%lld\n",ans);}
}
这篇关于poj1091 跳蚤 解不定方程 容斥原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
