北大poj-1091

跳蚤

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 9591   Accepted: 2892

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

Hint

这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)

Source

 
分析:很经典很经典的数论题目,为了做这道题目真是又学习了一把 欧几里得原理 和 容斥原理。这道题目学习为主。
参考:http://blog.csdn.net/crescent__moon/article/details/19327879?utm_source=tuicool&utm_medium=referral
解题:

给你两个正整数n,m,让你求长度为n+1的满足条件的一个等式:a[1]*x1+a[2]*x2+a[3]*x3+...+a[n]*xn+a[n+1]*x(n+1)=1 (0<=a[i]<=m&&a[n+1]=m)

让你求一共有多少种情况满足这个条件。

要使得 a[1]*x1+a[2]*x2+a[3]*x3+...+a[n]*xn+a[n+1]*m=1 (0<=a[i]<=m),那么a[1],a[2],a[3]....a[n+1]的最大公约数为1.

要解决此题,你需要知道的知识有扩展欧几里得,鸽巢原理,以及递归求所有的排列组合。

许多博客都举了这么一个例子:

例如:n=2,m=360 
360=3^2*2^3*5  所有不满足条件的数列,最大公约数是360质因子的乘积,只要将这些组合去掉,就是要求的答案(不懂的慢慢揣摩)

那么就要先求出m的所有质因子,然后求出总的排列组合的个数,即题目中说的M^N,最后根据鸽巢原理求得最后答案。

公式为:ans=M^N-(有奇数个公因数的n元组)+(有偶数个公因数的n元组)。拿上面的例子来说就是

ans=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 个.

 
 //容斥原理  + 欧几里得原理
#include<stdio.h> #define M 100000 long long factors[M],reorder[M];
long long n,m,factorNum,per; void factoring()//分解质因子,存在factors里面
{
factorNum=;
long long max=m;
int i = ;
for(i=;i*i<=max;i++)
{
if(max%i==)factors[factorNum++]=i;
while(max%i==)max/=i;
}
if(max!=)factors[factorNum++]=max;
} long long power(long long base, long long index)//求x^y
{
long long k=base;
long long i = ;
for(i=; i<index; i++)
base*=k;
return base;
} void dfs(long long start,long long pos,long long FactorNum4Reorder)
{
long long i = ;
if(pos==FactorNum4Reorder)
{
long long t=m;
for(i=; i<FactorNum4Reorder; i++)
{
t/=reorder[i];//t表示每位上有几个包含质因子的数
}
per+=power(t,n);//总共有多少个
}
else
{
for(i=start; i<factorNum; i++)//递归回溯求解所有排列组合
{
reorder[pos]=factors[i];
dfs(i+,pos+,FactorNum4Reorder);
}
}
} int main()
{
long long i = ;
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
factoring();
long long ans=power(m,n);
for(i=; i<=factorNum; i++)
{
per=;
dfs(,,i);
if(i%)ans-=per;//如果有奇数个公因数的n元组就相减
else ans+=per;//如果有奇数个公因数的n元组就相加
}
printf("%I64d\n",ans);
}
return ;
}
上一篇:DateTable利用NPOI导出Excel 公共方法


下一篇:小程序新能力-个人开发者尝鲜微信小程序