题目
思路来源
乱搞ac
题解
枚举gcd，gcd一定是x的因子，
由于lcm+gcd=x，有lcm/gcd+1=x/gcd，还有lcm/gcd>=1
枚举lcm/gcd=y，
显然如果gcd>1，让gcd和lcm同除以gcd即可，所以可以认为gcd=1，
问题转化为，大小为k的集合，k个不同的数，满足gcd=1，且lcm=y的方案数，
然后写了个大暴力容斥，没想到过了…
dp[i][S]表示约数里当前选了i个数，当前所有质因子的状态有没有覆盖住最高幂次，
第j个质因子覆盖住了最高幂次就是1，否则就是0
但是，这个只能限制住lcm的限制，不能限制住gcd=1，所以容斥
用gcd=1的，减去gcd>1的，枚举大于1的具体是几，
比如需要减去的是gcd=2，lcm=y的方案，就等价于减去gcd=1,lcm=y/2的方案
减去所有大于的就正好是等于的了
代码
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
const int N=1e6+5,M=2e6+10,mod=1e9+7;
int x,k,ans;
struct Factor{
typedef long long ll;
static const int N=2304;// https://oeis.org/A066150
int p[N],num[N],d[N],st[N],up[N],c;
ll v[N];
map<int,int>fac;
Factor(){
init();
}
void init(){
c=0;
fac.clear();
}
// 质因数分解，视情况可以换为pollard_pho
void cal_f(int x){
for(int i=2;1ll*i*i<=x;++i){
while(x%i==0)x/=i,fac[i]++;
}
if(x>1)fac[x]++;
}
// x=prod{v in x}，获取x的每个质因子值p，出现个数num
void get_p(int v){
cal_f(v);
for(auto &w:fac){
p[c]=w.first;
num[c]=w.second;
up[c]=1;
rep(i,1,num[c])up[c]*=p[c];
//printf("c:%d p:%d num:%d up:%d\n",c,p[c],num[c],up[c]);
c++;
}
}
// x=prod{v in x}, 获取x的每个因子值v，因子个数前缀积d
void get_d(int x){
//printf("x:%d\n",x);
get_p(x);
v[0]=d[0]=1;
st[0]=0;
for(int i=0;i<c;++i){
d[i+1]=d[i]*(num[i]+1);
for(int j=d[i];j<d[i+1];++j){
v[j]=v[j-d[i]]*p[i];
st[j]=st[j-d[i]];
if(v[j]%up[i]==0)st[j]|=(1<<i);
}
}
}
};
vector<int>f;
map<int,int>mp;
void add(int &x,int y){
x=(x+y)%mod;
}
int sol(int w){
if(mp.count(w))return mp[w];
Factor g;
g.get_d(w);
int c=g.c,tot=g.d[c];
if(tot<k)return mp[w]=0;
int up=(1<<c)-1,res=0;
vector<vector<int>>dp(k+2,vector<int>(up+5,0));
dp[0][0]=1;
for(int i=0;i<tot;++i){
for(int j=k-1;j>=0;--j){
for(int x=up;x>=0;--x){
add(dp[j+1][x|g.st[i]],dp[j][x]);
}
}
}
res=dp[k][up];
//printf("w:%d\n",w);
for(int i=0;i<tot;++i){
if(g.v[i]==1)continue;
res=(res-sol(w/g.v[i])%mod)%mod;
res=(res+mod)%mod;
}
//;printf("w:%d res:%d\n",w,res);
return mp[w]=res;
}
int main(){
sci(x),sci(k);
for(ll i=1;i*i<=x;++i){
if(x%i==0){
f.pb(i);
if(x/i!=i)f.pb(x/i);
}
}
for(auto &g:f){
int w=x/g-1;
if(w<=0)continue;
add(ans,sol(w));
}
pte(ans);
return 0;
}