min_25筛：DIVCNTK
xenonex
2018-12-18 17:23:59
三倍经验题
```cpp
#include<cstdio>
#include<cmath>
#define SN 100010
typedef unsigned long long LL;
int sqr,prime[SN],pcnt;
LL N,k,v[SN],g1[SN],g2[SN],pre[SN],pre2[48];
bool isnp[SN];
void sieve()
{
for(int i=2;i<=SN;i++)
{
if(!isnp[i])prime[++pcnt] = i;
for(int j=1,k;j<=pcnt&&(k=i*prime[j])<=SN;j++)
{
isnp[k] = 1;
if(i%prime[j] == 0)break;
}
}
}
void work_g(LL n)
{
int i,j,t2; LL end,val,t1;
sqr = sqrt(n);
for(i=1,j=0;i<=sqr;i++)g1[i] = i-1, g2[i] = (v[++j]=n/i)-1;
for(j=1;prime[j]<=sqr;j++)
{
end = (LL)prime[j]*prime[j];
for(i=1;i<=sqr&&(val=v[i])>=end;i++)
t1 = val/prime[j], g2[i] += j-(t1 <= sqr? g1[t1]:g2[n/t1])-1;
if((LL)sqr >= end)for(i=sqr,t2=end;i>=t2;i--)g1[i] += j-g1[i/prime[j]]-1;
}
for(i=1;i<=sqr;i++)g1[i] *= (k+1), g2[i] *= (k+1), pre[i] = -(k+1)*(i-1);
for(i=0;i<48;i++)pre2[i] = k*i+1;
}
LL work_s(LL n,int q) //这个s不是标准写法
{
if(prime[q] > n)return 0;
if((LL)prime[q]*prime[q] > n)return (n <= sqr? g1[n]:g2[N/n])+pre[q];
LL ans = 0,pc; int e = 1;
for(pc=prime[q];pc<=n;pc*=prime[q],e++)ans += (work_s(n/pc,q+1)+1)*pre2[e];
return ans+work_s(n,q+1);
}
int main()
{
int T;
sieve(), scanf("%d",&T);
while(T--)scanf("%llu%llu",&N,&k), work_g(N), printf("%llu\n",work_s(N,1)+1);
return 0;
}
```