题目链接：http://codeforces.com/problemset/problem/900/D
题意：
给定x,y，问你有多少个数列a满足gcd(a[i]) = x 且 ∑(a[i]) = y。
题解：
由于gcd(a[i]) = x，所以y一定是x的倍数，否则无解。
那么原题就等价于：问你有多少个数列a满足gcd(a[i]) = 1 且 ∑(a[i]) = y/x。
设f(k)为gcd(a[i]) = 1 且 ∑(a[i]) = k时的答案。
只满足条件∑(a[i]) = k的数列共有2^(k-1)种（隔板法）
然后要从中去掉gcd不为1的数列。
每个和为k且gcd不为1的数列a1，对应着一个和为k的因数且gcd为1的数列a2。
因为a1可以由a2整体放大而来。
那么也就是f(k) = 2^(k-1) - ∑ f(p)，其中p为k的因数(p != k)。
搜索 + map记忆化即可。
由于需要用到的f(k)，k均为y/x的因数，最多sqrt(y/x)个。
加上map的log复杂度，所以总复杂度为O(sqrt(n)*log(n))。
AC Code:
1 #include
2 #include
3 #include <string.h>
4 #include