题意:若一个数n能被表达为n的k个因数的和(因数可重复使用),则称n是k表达数
多组测试数据T,求A~B的k表达数数量
数据范围:A,B<=1e18,T<=5e4,2<=k<=7
解析:这题第一眼看过去极其不可做,我考试时直接放弃
有一个比较显然的性质,如果一个数是k表达数,那么它的倍数一定都是k表达数.
如果n = ∑(k|n)k,那么显然有x*n = Σ(x*k|x*n)x*k;
所以可以猜想对于每个k我们都可以找出它的几个最小k表达数xi,且任意i,j都不满足xi|xj，然后它们的所有倍数都是k表达数
爆搜一下可以发现xi很小且很少
如:k = 2 : 2(1 + 1)
= 3 : 3(1 + 1+ 1) 4(1 + 1 + 2)
= 4: 4(1 + 1 + 1 + 1) 6(1 + 2 + 2 + 1) 10(2 + 2 + 5 + 1)
即使等于7也只有15个xi,所以转化为经典问题,问A~B之间有几个数是给定的数的至少一个的倍数,容斥一下即可
注意暴力容斥2^15 * T是过不了的,所以需要开个Map记录一下,各个最小公倍数的贡献(因为最小公倍数可能会重复,如24,54,36的最小公倍数与24,54的最小公倍数是相同的),奇加偶减即可
代码如下:
/*divisor*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
#define ll long long
ll read(){
char c = getchar();
ll x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar();
return x;
}
const int maxn = 1e5 + 10;
map<ll,ll>Map[11];
vector<int>valid[11];
vector<int>pr[510];
int a[maxn];
bool used[11][510];
vector<int>num[11];
vector<int>op[11];
ll gcd(ll x,ll y){
return (y == 0)?x:gcd(y,x%y);
}
ll lcm(ll x,ll y){
return x / gcd(x,y) * y;
}
bool Dfs(int x,int n,int step,int k){
if(step == k + 1){
ll g = 0;
ll sum = 0;
for(int i = 1; i <= k; ++i)
g = gcd(g,a[i]),sum += a[i];
if(g == 1 && sum == x) return true;
return false;
}
for(int i = n; i < (int)pr[x].size(); ++i){
int v = pr[x][i];
a[step] = v;
if(Dfs(x,i,step+1,k)) return true;
a[step] = 0;
}
return false;
}
int main(){
for(int i = 1; i <= 500; ++i)
for(int j = 1; j * i <= 500; ++j)
pr[j*i].push_back(i);
int t = read();
while(t--){
ll a = read(),b = read(),k = read();
if(!Map[k][0]){
for(int i = 1; i <= 500; ++i){
if(Dfs(i,0,1,k)){
bool flag = 1;
for(int j = 0; j < (int)pr[i].size(); ++j){
if(used[k][pr[i][j]]){
flag = 0;
break;
}
}
if(flag)
valid[k].push_back(i),used[k][i] = true;
}
}
Map[k][0] = 1;
int n = valid[k].size();
int tot = -1;
for(int i = 1; i < (1 << n); ++i){
ll lc = 1;
int cnt = 0;
for(int j = 0; j < n; ++j){
if(i & (1 << (j))) cnt++,lc = lcm(lc,valid[k][j]);
}
int o = (cnt & 1)?1:-1;
if(!Map[k][lc]){
Map[k][lc] = ++tot;
num[k].push_back(lc),op[k].push_back(o);
}
else{
op[k][Map[k][lc]] += o;
}
}
}
ll Ans = 0;
for(int i = 0; i < (int)num[k].size(); ++i){
ll v = num[k][i],o = op[k][i];
Ans += o * ((b / v) - ((a - 1) / v));
}
printf("%lld
",Ans);
}
return 0;
}