题目链接：Codeforces 439E Devu and Birthday Celebration

题目大意：给出q，表示询问的次数，每次询问有n和f，问有多少种分类方法，将n分成f份，并且这f份的最大共约数为1.

解题思路：如果不考虑说最大共约数为1的话，那么问题很简单，就是f个数的和为n的种数C(f?1n?1).所以我们就尽量将问题转化成说f数的和为s的子问题。用容斥原理，总的可能减去公约数不为1的情况，那么公约数不为1的情况就去枚举公约数。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int N = 1e5+5; const int MOD = 1e9+7; vector
        
          vec; int fact[N], ive_fact[N]; int power (int x, int n) { int ans = 1; while (n) { if (n&1) ans = (1ll * ans * x) % MOD; n /= 2; x = (1ll * x * x) % MOD; } return ans; } void init () { fact[0] = 1; for (int i = 1; i < N; i++) fact[i] = (1ll * fact[i-1] * i) % MOD; for (int i = 0; i < N; i++) ive_fact[i] = power(fact[i], MOD-2); } void divFactor(int cur) { vec.clear(); int tmp = sqrt(cur+0.5); for (int i = 2; i <= tmp; i++) { if (cur % i == 0) { vec.push_back(i); while (cur % i == 0) cur /= i; } } if (cur != 1) vec.push_back(cur); } int solve (int n,int f) { if (n < f) return 0; int ans = fact[n]; ans = 1ll * ans * ive_fact[f] % MOD; ans = 1ll * ans * ive_fact[n-f] % MOD; return ans; } int cal (int n) { return (n % MOD + MOD) % MOD; } int main () { init(); int cas; scanf("%d", &cas); while (cas--) { int n, f; scanf("%d%d", &n, &f); divFactor(n); int ans = 0, t = 1<