无聊的题目
感觉很高妙，果然我什么都不会。
我给洛谷送了这么多钱，看一道去年省选计划的题不过分吧。。。
题面描述：
对 $ n = p _ 1 ^ { a _ 1 } p _ 2 ^ { a _ 2 } \cdots p _ k ^ { a _ k }$，定义：
$$ f ( n ) = \min \{ a _ 1 , a _ 2 , \cdots , a _ k\} \times \max \{ a _ 1 , a _ 2 , \cdots , a _ k \}$$
特别地，规定 $ f ( 1 ) = 0$，求：
$$ \sum _ { i = 1 } ^ { n } f ( i )$$
数据范围：$ n \le 10 ^ { 1 2 }$。
设满足 $\max \{ a _ 1 , \cdots , a _ k\} = v$ 的数 $x$ 的个数为 $f(v)$。
设满足 $\max \{ a _ 1 , \cdots , a _ k\} \le v$ 的数 $x$ 的个数为 $g(v)$。
可以知道 $f ( v )= g ( v ) - g( v - 1 )$。
然后我们的 $g ( v ) $ 可以容斥计算：
$$g ( v ) = \sum _ { d = 1 } \mu ( d ) \left\lfloor \dfrac {n} {d ^ { v + 1 }} \right\rfloor$$
意义不解释。。。
然后就有了 $f(v)$。
接着暴力枚举 $\min \ge 2 $ 的数。
具体做法是筛出 $\sqrt{n}$ 内的质数，暴力枚举质数指数的所有排列组合，并且保证没有一个数的指数为 1，很容易证明，这个复杂度是 $O(\sqrt{n}\log n)$ 的，这一部分的答案就这么解决了。并且记得在过程中把统计过的 $f( \max )$ 给减掉。
剩下的全都是 $\min = 1 $ 的数，那么只和 $\max$ 有关了，直接统计即可。
至于拓展到二元函数（不仅仅是乘法，任何复杂度较低的运算）情况，也都是如此。
时间复杂度是 $O(\sqrt { n} \log n)$ 的。
代码：
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<iostream>
#include<cstdio>
#define ll __int128
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=2e6,inf=3200;
ll n,cnt,ans;
ll prime[N+5],mu[N+5],g[N+5],f[N+5];
bool ff[N+5];
inline void Init() {
ff[1]=1;mu[1]=1;
for(ll i=2;i<=N;i++) {
if(!ff[i]) {prime[++cnt]=i;mu[i]=-1;}
for(ll j=1;j<=cnt&&prime[j]*i<=N;j++) {
ff[i*prime[j]]=1;
if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
mu[i*prime[j]]=-mu[i];
}
}
}
inline void Dfs(ll x,ll step,ll ma,ll mi) {
if(x*prime[step]*prime[step]>n) return;
Dfs(x,step+1,ma,mi);x=x*prime[step];if(x>n) return;
for(ll i=2;x<=n;i++) {
x=x*prime[step];if(x>n) return;
ll tmpma=max(ma,i),tmpmi=min(mi,i);
ans+=tmpma*tmpmi;f[tmpma]--;
Dfs(x,step+1,max(ma,i),min(mi,i));
}
}
inline ll Pow(ll b,ll p) {
ll r=1;while(p) {if(p&1) r=r*b;b=b*b;p>>=1;}return r;
}
int main() {
n=read();Init();
g[0]=1;f[0]=1;
for(ll v=1;v<=40;v++) {
for(ll i=1;i<=n;i++) {
ll tmp=Pow(i,v+1);if(tmp>n) break;
g[v]+=mu[i]*(n/tmp);
}
f[v]=g[v]-g[v-1];
}
Dfs(1,1,0,inf);
for(ll i=1;i<=40;i++) ans+=f[i]*i;
write(ans);
return 0;
}
|