题目大意
有人问现实中为什么总是男生追求女生，反过来很少。实际上女生也是想主动追求男生的，但是世俗中对于主动追求男生的女生有种歧视，这样就使得女生不大敢主动追求男生。但是面对喜欢的男生，难道就不出手么？女生只能步步为营，挖坑来引诱男生往里跳。这时候问题就来了，挖掘机技术到底哪家强？
被热血沸腾的广告洗脑了若干天后，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;
}
|
