隐藏
「bsoj5140」挖掘机技术哪家强 - 数论 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj5140」挖掘机技术哪家强 - 数论

题目大意

    有人问现实中为什么总是男生追求女生,反过来很少。实际上女生也是想主动追求男生的,但是世俗中对于主动追求男生的女生有种歧视,这样就使得女生不大敢主动追求男生。但是面对喜欢的男生,难道就不出手么?女生只能步步为营,挖坑来引诱男生往里跳。这时候问题就来了,挖掘机技术到底哪家强?
    被热血沸腾的广告洗脑了若干天后,Matt终于下定决心,毅然登上了开往泉城的列车,决心寻找生活的希望。
    来到布鲁谢特学院后,Matt逐渐地了解了各种型号的挖掘机。在这里我们可以认为有大挖掘机和小挖掘机两种。
    今天Matt的任务很简单:首先他要用大挖掘机挖出恰好$N$单位体积的砂土。由于小挖掘机比较笨拙,它每次挖的砂土体积是固定的。也就是说,设每次挖$x$单位体积砂土,那么$N$需要被$x$整除。在挖出若干堆体积为$x$的砂土后,Matt需要计算$x$的“难挖指数”。体积$x$的“难挖指数”定义如下:对于某个不超过$x$的体积$y$,如果$x$与$y$的最大公约数为$1$,那我们认为体积$y$是“难挖的”,$x$的“难挖指数”就要加上$y$。
    由于Matt之后还需要用小挖掘机处理被大挖掘机挖出的砂土,他希望知道所有可能的$x$的难挖指数的和,这样他好估算今天要干多久,不然作为布鲁谢特的高才生,他出门要被笑话的。


题目分析

题目要求的是:

令$f(x)=\sum_{i=1}^x[\gcd(x,i)=1]i$,则:

我们可以枚举$n$的约数,在$\sqrt n$的时间内可以完成。
接下来我们要快速计算出$f(x)$的值。

不难发现$f(x)$即为在$x$内与$x$互素的数之和。
这可以用欧拉函数解决,因为若$\gcd(i,x)=1$,则$\gcd(x-i,x)=1$,因此必定有两个互素的满足条件的数相加正好为$x$,故$f(x)=n\times\frac{\phi(x)}2$。

注意这个结论对$x=1$时不适用,因此答案要$+1$。

现在要快速计算$\phi(x)$,$x\le10^7$时直接线性筛即可。
当$x\gt10^7$时,可以根据公式使用素数直接暴力计算。

achen:这个式子不是很容易就反演出来了嘛。


代码

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
75
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=1e7+5;
int t,n,Phi[maxn],vst[maxn],Prime[maxn],cnt=0;

void Phi_Table(int n) {
Phi[1]=1;
for(int i=2; i<=n; i++) {
if(!vst[i]) {
Prime[++cnt]=i;
Phi[i]=i-1;
}
for(int j=1; j<=cnt&&Prime[j]*i<=n; j++) {
vst[Prime[j]*i]=1;
if(i%Prime[j]==0) {
Phi[i*Prime[j]]=Phi[i]*Prime[j];
break;
}
Phi[i*Prime[j]]=Phi[i]*Phi[Prime[j]];
}
}
}

LL Cal_Phi(LL x) {
if(x<=1e7)return Phi[x];
LL ans=x;
for(int i=1; i<=cnt&&Prime[i]<=sqrt(x); i++)
if(x%Prime[i]==0) {
ans-=ans/Prime[i];
while(x%Prime[i]==0)x/=Prime[i];
}
if(x>1)ans-=ans/x;
return ans;
}

int main() {
Phi_Table(1e7);
t=Get_Int();
while(t--) {
LL ans=0;
n=Get_Int();
for(int i=1; i<=sqrt(n); i++)
if(n%i==0) {
ans+=(Cal_Phi(i)*i)>>1;
if(n/i!=i)ans+=(Cal_Phi(n/i)*n/i)>>1;
}
printf("%lld\n",ans+1);
}
return 0;
}
姥爷们赏瓶冰阔落吧~