题目链接

HDU4746

思路

这套题可以用前缀和的思想优化确实挺好，不过其实就是一个提取公因式的问题
首先根据套路莫比乌斯反演我们显然可以O(qnlogn)求出来，但是很明显会超时所以我们需要优化。
把答案的式子写出来之后我们可以枚举$\mu(i)$也就是枚举莫比乌斯函数值，然后通过分块优化，可以在O(nq)内求出答案

题目链接

HDU4675

思路

首先这道题难的地方就是组合数学的地方，另一部分可以用很简单的莫比乌斯反演来写。
我们来分析k个a[i]≠b[i]，这个条件
假设gcd(b[])=d,那么b中肯定全都是d的倍数，所以我们需要把a[]中所有非d的倍数变成d的倍数，然后如果超过k个，那么肯定无法只有k个不同，所以答案是0
如果不超过k个，那么我们还需要从d的倍数中挑选出k-(n-num[d])个。
所以最后

题目链接

HYSBZ2005

思路

根据题目意思，很明显跟gcd有关，因为路径上若有经过的点则点的个数为gcd(a,b)-1的个数
然后这题的答案就是求

按照套路来
设f(n)为gcd(a,b)=n的个数
则F(n)为gcd(a,b)=n及n的倍数的个数
答案就变为

题目链接

HYSBZ-2818

思路

这道题思路略微复杂，主要是需要交换枚举对象。
首先明确我们要求的答案

按照套路来
设f(n)为gcd(a,b)=n的个数
则F(n)为gcd(a,b)=n及n的倍数的个数
然后可以转化为

题目链接

HDU1695

思路

题目要求的是下面这个式子

转化一下变成

然后就可以用莫比乌斯反演来求了
设f(n)为gcd(a,b)=n的个数
则F(n)为gcd(a,b)=n及n的倍数的个数
则有

题目链接

SPOJ - VLATTICE-莫比乌斯反演

思路

首先这题很容易转成

因为如果gcd(i,j,k)=g≠1，则必有gcd(i/g,j/g,k/g)=1;
然后用莫比乌斯反演套路直接设
设f(n)为gcd(a,b,c)=n的个数
则F(n)为gcd(a,b,c)=n及n的倍数的个数
则有

题目链接

poj-3904

思路

莫比乌斯反演很好的一道入门题。这里运用莫比乌斯倍数反演.
设f(n)为gcd(a,b,c,d)=n的个数
则F(n)为gcd(a,b,c,d)=n及n的倍数的个数
则有

然后用莫比乌斯倍数反演得到

题目链接

SDOI2011

思路

第一个方法，快速幂，很简单；
第二个解决方法，扩展欧几里得定理，这里不细说；
第三个BSGS,大步小步算法（北上广深）
设有

因为gcd(y,p)=1；
我们可以令$x=km-a$
整个式子就变成

然后枚举右边的小步1~a，用hash记录一下，然后枚举左边的大步，判断是否有解即可；
还有扩展BSGS…（先挖坑）

题目链接

Digit sum

思路

这题就是计算1-n的各个位数之和，那么我们可以对每个位置进行统计。
例如，328，
先看百位
3(28+1)
2100
1100
再看十位
2(8+1)
110
这时候需要计算111 112 中的十位
也就是1+2+3+4+5+6+7+8+9=45,计算有多少个45.注意，这时候先不看个位。我们有110 120 130 140 150 160 ~290 ，也就是有3组，就是34510.
然后再看个位8+7+6+5+4+3+2+1，然后4532*1；
就好了

题目链接

Honk’s-pool(思维)

题目描述

给出一个数组，每次给最小的加一，最大的减一，执行k此，问最后的数组最大值与最小值的差。

思路

这道题有些坑点，但是其实很简单，就是先找出数组中最小值最大化，在找出最大值最小化，然后记得判断这个数组能否变成全为一个数字的情况。
例如1 2 2 3这样的。用二分来判断就可以。然后如果sum%n==0的话，并且最小值大于等于最大值，那么答案就是0，否则答案就是1.
如果最小值小于最大值，答案就是他们之间的差值。