Question

C语言很有意思的题 跳扫（汗...我的输入法里面没那个字），求数学理论根据，高手请进

18:跳蚤

* 查看
* 提交
* 统计
* 提问

时间限制:
5000ms
内存限制:
65536kB

描述
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张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。
输入
两个整数N和M(N <= 15 , M <= 100000000)。
输出
可以完成任务的卡片数。
样例输入
2 4
样列输出
12
提示：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)
我现在有算法了，但是嵌套跟这个N成线性，我觉的这道题应该没那么复杂，可能有数学的公式在里面，希望有高手能指点下。
请问：判断一个数在比它小的数中有多少个是互质的，最快捷的算法是什么？

答案满意的给20分

Answer 1

的确是很有意思的题目。
我不是学计算数学的，暂时也没有很好的思路。坐等高手吧

Answer 2

含1的所有都可以,按你先前例子都可以跳到,比如1,2,3先1左跳6或又跳4,再23右跳或左跳.怎么没有？

追问

不对，你没有含4

Answer 3

我只讲算法，不写程序：
这个问题可以看成是，枚举所有的x1,x2,x3...xn，xi<=N，使得这些所有的xi的最小公约数必须等于1即可。
然后，组合一共有M^N种，我们只需从中减去最小公约数不是1的那部分即可。
于是，首先对M因式分解，求出其所有的质因子，然后通过容斥原理进行计数。
下面举个例子。
如果 N=3，M=18
那么组合共有18^3=104976种
18因式分解：
18=2*3*3
然后按照如下的组合进行容斥归并
被2整除的有18/2=9个数，对应9^3=729种选择（选前三个数，每个数3种选择，乘法原理）
被3整除的有18/3=6个数，对应6^3=216种
被3整除的有18/3=6个数，216种
于是剩下104976-729-216-216种
但是前面的减多了，为什么，因为有同时被2和3或者同时被两个3整除的这些被重复算了，我们要加回来。
被2和3同时整除的有18/2/3=3个数，对应3^3=27种
被2和3同时整除的有18/2/3=3个数，对应3^3=27种
被3和3同时整除的有18/3=6个数，对应6^3=216种
加回来，于是剩下104976-729-216-216+27+27+216种
但是又加多了，要减回同时被2,3,3整除的1个，即
18/2/3=3个数，对应3^3=27种
最后的结果是：104976-729-216-216+27+27+216-27=104058种

算法描述如上，编程就不说了，如想进一步了解或有疑问直接找我发私信或追问，欢迎指正。
如需编程指导请追分。

另外，这个结果太巨大了，肯定要用大数模板解决。

Answer 4

我想错了

而是只要存在最小公约数为1的组就行

追问

那前面的就不符合阿

追答

楼上的计算方法是错的，3,18 也可以排出 5,5,10这样的，也跳不出来

真要根据容拆原理，那要计算的是小于M的所有情况，这个复杂的容拆原理的公式我是记不得了

这个可以看着是有序的，那么从小到大
由第一个开始，如果是1后面的就不考虑了全是
如果不是1，放第二个数如果是互质的后面全是，否则就出公约数，继续放第三个
如此递归