题目传送门

大致题意:

定义$d(x)$为把$x$拆分为$A*A*B(1\leq A\leq B)$的方案数。求$\sum^{b}_{x=a} d(x)$。

$1\leq a \leq b \leq 10^{15}$


Solution

首先,$[1,n]$中被$k$整除的个数有$\lfloor \frac{n}{k} \rfloor$个。

转换一下题目,就是要求满足$[a,b]$中满足$i^3\leq x $ 且$i^2 | x$的$x$的个数。

先不管前一个条件,如果只需要满足$i^2|x$该如何实现?

只需要枚举$i^2$,并累加$\lfloor \frac{n}{i^2} \rfloor$到答案上。

但因为我们只能快速求得$[1,n]$中被$i^2$整除的数的个数,所以考虑用类似前缀和的东西,用$[1,b]$的答案减去$[1,a-1]$的答案。

那么问题转化为了求$[1,n]$间满足条件的个数。那么就枚举$1\leq i^2\leq n$即可。

但由于$x$要满足$i^3 \leq x$,所以累加的应该是$[i^3,n]$之间被$i^2$整除的数。那么累加的就改为$\lfloor \frac{n}{i^2}\rfloor - \lfloor \frac{i^3-1}{i^2} \rfloor$。

显然$n$要大于$i^3$,那么枚举$i$的上界到$\sqrt[3] n$即可。

$10^{15}$注意longlong。

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll solve(ll b)
{
    ll B=cbrt(b),ans=0;
    for(ll i=1;i<=B;i++)
        ans+=(b/(i*i)-((i*i*i-1ll)/(i*i))); 
    return ans;
}
int main()
{
    ll ans=0,a,b;
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",solve(b)-solve(a-1));
    return 0;
}
最后修改:2020 年 08 月 28 日 08 : 32 AM