Title
GCD
Solution
注意一定要把思路清晰了，然后再实现，加快码题的效率 当
x
x
x包含相等的质因子(
x
α
x^\alpha
xα(
x
∈
p
r
i
m
e
x \in prime
x∈prime))时，
a
n
s
+
=
x
ans+=x
ans+=x 否则因为都是质因数，所以总的
g
c
d
gcd
gcd是
1
1
1 类似莫比乌斯函数
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std
;
const ll N
=1e7+5;
ll a
,b
,m
,v
[N
],prime
[N
],ans
; bool q
[N
];
void linear(ll k
){
for(ll i
=2;i
<=k
;i
++){
if (!v
[i
]) v
[i
]=i
,prime
[++m
]=i
,q
[i
]=1;
for(ll j
=1;j
<=m
;j
++){
if (prime
[j
]>v
[i
]||prime
[j
]>k
/i
) break;
v
[i
*prime
[j
]]=prime
[j
];
if (v
[i
]==prime
[j
]&&q
[i
]&&q
[prime
[j
]]) q
[i
*prime
[j
]]=1;
}
}
}
int main(){
scanf("%lld%lld",&a
,&b
);
if (a
>b
) swap(a
,b
);
linear(b
);
for(ll i
=a
;i
<=b
;i
++)
if (q
[i
]) ans
+=v
[i
]; else ans
++;
printf("%lld",ans
);
}
