Fork me on GitHub

Codeforces665F

Codeforces665F题解

题意:

  • 让你求出满足$x \leq n$且$d(x)=\sum_{d|x}=4$的$x$的个数。
  • $n \leq 10^{11}$

题解:

  • $x=\prod_{i=1}^{k} p_i^{a_i},d(x)=\prod_{i=1}^{k}a_i+1$
  • $d(x)=4$
  • 可以得到:
  • 前者非常好统计,后者如果算上完全平方数,就相当于等于两素数乘积的数的个数,设为$Ans$。
  • 考虑枚举小于等于$\sqrt{n}$的素数。
  • 其中$f(x)$表示小于等于$x$的素数个数。
  • 然后我们听说一个叫做洲阁筛的东西。它的第一部分就是在求这个东西的。
  • 于是借此机会学习了一下。
  • 设$g_k(i,j)$表示$1 \cdots j$中与前$i$个质数均互质的数的$k$次方和。
  • 那么在求$f(p_i)$时,可以直接线性筛得到。
  • 而$f(\lfloor \frac{n}{p_i} \rfloor)=g_0(m,n)+m$
  • $m$表示小于等于$\sqrt{n}$的质数个数。
  • 因为$j$的取值只有$O(\sqrt{n})$种,所以暴力复杂度$O(\frac{n}{logn})$。
  • 然而如果$p_i^2>j$时:
  • 所以可以对于$p_{i_0}^{2}>j$时开始便不再转换。若需要$g_k(i_1,j)$的值,$i_1>=i_0$,就通过$g_k(i_1.j)=g_k(i_0,j)-\sum_{i=i_0+1}^{i_1}p_i^k$计算得到。
  • 时间复杂度分析:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define ll long long
#define N 1000009
using namespace std;
ll n,pd[N],pri[N],cnt,g[2][N],m=1;
struct hash
{
#define mod 19260817
ll first[mod],number;
struct edge
{
ll to,next,id,g,delta;
void add(ll x,ll _id,ll _g,ll _delta,ll fir)
{
next=fir;
id=_id,g=_g,delta=_delta;
}
}e[N];
edge &operator [](const ll &_x)
{
int x=_x%mod;
for (ll i=first[x];i;i=e[i].next)
if (e[i].id==_x) return e[i];
e[++number].add(x,_x,0,0,first[x]),first[x]=number;
return e[number];
}
#undef mod
}mp;
void init()
{
ll num=0;
for (ll i=1;i<=n;i=(n/(n/i))+1)
num++,mp[n/i].g=n/i,mp[n/i].delta=0;
for (ll i=1;i<=m;i++)
for (ll j=1;pri[i]*pri[i]<=n/j;j=(n/(n/j))+1)
{
ll now=n/j/pri[i];
mp[n/j].g-=mp[now].g-(i-1-mp[now].delta);
mp[n/j].delta=i;
}
}
ll get(ll x)
{
return mp[x].g-(m-mp[x].delta);
}
ll work()
{
while (pri[m]*pri[m]<=n) m++;
m--;
ll ret=1;
while (pri[ret]*pri[ret]*pri[ret]<=n) ret++;
ret--;
init();
for (int i=1;pri[i]*pri[i]<=n;i++)
ret+=get(n/pri[i])-get(pri[i]);
return ret;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
pd[1]=1;
for (int i=2;i<N;i++)
{
if (!pd[i]) pri[++cnt]=i;
for (int j=1;j<=cnt&&pri[j]*i<N;j++)
{
pd[pri[j]*i]=1;
if (!(i%pri[j])) break;
}
}
cin>>n;
cout<<work()<<endl;
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces665F

文章作者:wzf2000

发布时间:2017年12月26日 - 07:12

最后更新:2017年12月26日 - 09:12

原始链接:https://wzf2000.github.io/2017/12/26/Codeforces665F/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。