FZU-2191 完美的数字 简单数论

题目传送门

大致题意：

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

(1leq a leq b leq 10^{15})

---

Solution

首先，([1,n])中被(k)整除的个数有(lfloor frac{n}{k} floor)个。

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

先不管前一个条件，如果只需要满足(i^2|x)该如何实现？

只需要枚举(i^2)，并累加(lfloor frac{n}{i^2} floor)到答案上。

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

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

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

显然(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
",solve(b)-solve(a-1));
    return 0;
}