DLUTOJ 1330 GCD 【莫比烏斯反演+組合】

http://acm.dlut.edu.cn/problem.php?id=1330

1330: GCD

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 22   Solved: 6

[ Submit][ Status][ Web Board]

Description

How many non decreasing sequences are there of length K, with the condition that numbers in sequence can take values only from 1,2,3,⋯N and gcd of all numbers in the sequence must be 1.

Input

The first line contains an integer T i.e. the number of test cases. T lines follow, each line containing two integers N and K separated by a single space. 1≤T≤5  1≤N≤10^5  1≤K≤10^5

Output

For each testcase, print in a newline the answer mod(10^9+7).

Sample Input

42 4 3 45 21 10

Sample Output

413101

HINT

For the first testcase, the sequences are (1,1,1,1), (1,1,1,2), (1,1,2,2), (1,2,2,2) = 4

For the second testcase, the sequences are (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,2,2), (1,1,2,3), (1,1,3,3) (1,3,3,3), (1,2,2,2), (1,2,2,3), (1,2,3,3), (2,2,2,3), (2,2,3,3), (2,3,3,3) which are 13 in number.

For the third testcase, the sequences are (1,1), (1,2), (1,3), (1,4), (1,5), (2,3), (2,5), (3, 4), (3, 5), (4, 5) = 10

For the fourth testcase, the only sequence is (1,1,1,1,1,1,1,1,1,1)

Source

k個數可選範圍是1~n，問有多少個非降序列滿足他們的gcd為1

令f（x）代表n以内， 長度為x的，滿足題目要求且各個數字不相同的序列種類數。于是當k=4，n=3時，x=2時能夠組成的種類數是f(2)*C(k-1,x-1)。即1112,1122,1222  3種*f(2)。是以下面隻要求出f(x)的值便可得到答案。

假設需要選出x個不同的數字構成gcd=1的序列。g[d]代表長度為x的遞增序列，其gcd=d的倍數 序列個數。g[d]容易看出是C(n/d,x)，即從d的倍數中選出x個來組成序列。f[d]代表長度為x的遞增序列，gcd=d時的情況，上面的f(x)預設下d為1，因而省略。于是可以知道g[d]=∑d|n f(n)  =C(n/d,x)

由莫比烏斯反演公式可得f(1)=∑1<=i<=n (mu[i]*g[i])

本體組合數需要預先處理，并且mu函數和可能出現負值，需要取正

//#include<bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>

using namespace std;

#define For(i,a,b) for(int (i)=(a);(i) < (b);(i)++)
#define rof(i,a,b) for(int (i)=(a);(i) > (b);(i)--)
#define IOS ios::sync_with_stdio(false)
#define lson l,m,rt <<1
#define rson m+1,r,rt<<1|1
#define mem(a,b) memset(a,b,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;


void RI (int& x){
    x = 0;
    char c = getchar ();
    while (c == ' '||c == '\n')    c = getchar ();
    bool flag = 1;
    if (c == '-'){
        flag = 0;
        c = getchar ();
    }
    while (c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = getchar ();
    }
    if (!flag)    x = -x;
}
void RII (int& x, int& y){RI (x), RI (y);}
void RIII (int& x, int& y, int& z){RI (x), RI (y), RI (z);}

/**************************************END define***************************************/
const int maxn = 1e5+10;
const int INF =0x3f3f3f3f;
const int mod = 1e9+7;
bool flag[maxn];
int mu[maxn];
vector<int> prime;
ll A[maxn],inv[maxn],sum[maxn];
int n,k;
void get_prime_phi()
{
    mu[1]=1;
    For(i,2,maxn){
        if(!flag[i]){
            prime.push_back(i);
            mu[i]=-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<maxn;j++){
            flag[i*prime[j]]=true;
            if(i%prime[j]) mu[i*prime[j]]=-mu[i];
            else {
                mu[i*prime[j]]=0;
                break;
            }
        }
    }
    sum[0]=0;
    For(i,1,maxn) sum[i]=sum[i-1]+mu[i];
}
ll quick_mod(ll a,ll b)
{
    ll ans=1;
    a%=mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

ll getC(int n,int m)
{
    //if(n<m) return 0;
    return (((A[n]*inv[m])%mod)*inv[n-m])%mod;
}


void init()
{
    A[0]=inv[0]=1;
    for(int i=1;i<maxn;i++){
        A[i]=A[i-1]*i%mod;
        inv[i]=quick_mod(A[i],mod-2);
    }
}
ll f(int x)
{
    ll ans=0;
    for(int i=1,last=i; i<=n;i=last+1){
        last=n/(n/i);
        if(n/i<x) break;
        ans=(ans+(sum[last]-sum[i-1])*getC(n/i,x))%mod;
    }
    ans=(ans+mod)%mod;
    return ans;
}
ll solve()
{
    ll ans=1;
    int n_id=min(n,k);
    for(int i=2;i<=n_id;i++){
        ans=((ans+getC(k-1,i-1)*f(i)))%mod;
    }
    return ans;
}

int main()
{
    get_prime_phi();
    init();
    int T;
    RI(T);
    while(T--){
        RII(n,k);
        cout<<solve()<<endl;;
    }
}