题面
题目分析
令
则
此处表示小于等于
中,满足两个数互质且乘积为
的无序数对的个数,显然
其中
表示d的质因子个数
相当于把d的质因数分成两部分,所以就每个质因数选或不选,又因为是无序数对,所以除以2,也可以写为以下形式
- 有没有发现十分类似某个等式,记与
互质的数的和为
(随便选的字母),则
回到这道题,有
然后我们又发现其实是每个质因数选或不选的方案数,及
的无平方因子的约数的个数,所以
根据
函数的定义,我们知道只有无平方因子数的函数值才为1或-1,所以加上绝对值就成了计数
- 先看第二个
,对于某一个
的取值,把它记作
,就以
的范围做整除分块优化,
的时间复杂度,那么外层还有一个求和,于是在外面也套一层整除分块优化,预处理出前
后时间复杂度为
- 此处预处理为线性筛,考虑变换,
实际可看作枚举
后看
以内有多少个数能被
整除,这不就是
吗?(这个函数表示i的约数个数)
于是我们只需要筛出约数个数在累加就行了,线性筛时存一下当前数的最小质因子的次数就可以愉快的线性筛了
- 由于在外面一层套上了整除分块优化,则需要求出
的前缀和,也就是
以内的无平方因子数
- 这里处理无平方因子数时用容斥原理,有
想想
函数的定义,这个容斥还是比较好理解的
可处理出来
- 其实这道题用的是[SPOJ] DIVCNT2 - Counting Divisors (square)一模一样的方法(我后面的分析都是直接粘的233)
- 但是奈何这道题
的卡内存!(各种预处理+卡内存我只能做到6015ms>6000ms T了…)
- 只能想想别的办法(也许有些同学掌握特殊的卡常技巧能过A掉吧)
.
.
.
.
.
好的。
正文开始
那么我就要开始略讲一点了
定义
则
考虑怎么求
设,则
反演一下得到
不考虑
的话就是
三个数的乘积的统计,做法为统计
的
数对的数量
分别考虑三个数不相等/两个数相等/三个数相等的情况再分别乘上排列系数
由于这样的枚举只需要枚举,在枚举
,然后
统计
的个数
比较讨厌,假设
与
被统计两次,因为有
的情况不能直接除以
回到原问题,当时,由于
,所以
,此时
有
种取值,所以只需要在算出的结果加上
再除以
即可
参考自 51Nod 题解1楼
时间复杂度证明
设表示统计满足
的
的三元组个数的时间复杂度
上面的是枚举
时从
开始枚举,总时间复杂度
此处
的枚举应该是离散的,我们将它看做连续的,由于
那么将
两两结合,有
于是我们又回到离散的,最多有
对这样的关系,所以
所以总时间复杂度为
申明:以上的符号纯属乱用,只是不能再用
表示
的取值可能不为整数的和了
AC code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 316228;
int Cnt, Prime[N], mu[N];
bool IsnotPrime[N];
void init()
{
mu[1] = 1;
for(int i = 2; i < N; ++i)
{
if(!IsnotPrime[i])
Prime[++Cnt] = i, mu[i] = -1;
for(int j = 1; j <= Cnt && i * Prime[j] < N; ++j)
{
IsnotPrime[i * Prime[j]] = 1;
if(i % Prime[j] == 0) { mu[i * Prime[j]] = 0; break; }
mu[i * Prime[j]] = -mu[i];
}
}
}
LL solve(LL n)
{
LL ret = n;
for(int d = 1; (LL)d*d <= n; ++d) if(mu[d])
{
LL m = n/((LL)d*d), s = 0;
for(int a = 1; (LL)a*a*a <= m; ++a)
{
for(int b = a+1; (LL)a*b*b <= m; ++b)
s += (m/((LL)a*b)-b) * 6 + 3; // * 6 -> a < b < c ( P(3,3) = 6 )
// + 3 -> a < b = c ( P(3,3)/P(2,2) = 3)
s += (m/((LL)a*a)-a) * 3 + 1; // * 3 -> a = b < c ( P(3,3)/P(2,2) = 3 )
// + 1 -> a = b = c
}//以上的"-b","-a"都是为了满足 c>b 或 c>b=a,跟时间复杂度的分析一样
ret += s * mu[d];
}
return ret / 2;
}
int main ()
{
LL a, b; init();
scanf("%lld%lld", &a, &b);
printf("%lld\n", solve(b)-solve(a-1));
}
.
.
可写死我了