BZOJ 2705:
$sum_{i=1}^{n}gcd(i,n) (nle2^{32})$
2018 蓝桥国赛第六题：
$sum_{i=1}^{i=n}sum_{i=1}^{i=n}gcd (i,j)^2 (nle10^7)$
BZOJ 2705
- 枚举约数，求$phi$即可
- 注意枚举$i$的时候还有$frac{n}{i}$
- 时间复杂度$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
|
#define ll long long
using namespace std;
ll ans, n;
ll (ll x)
{
ll ans=x;
for(ll i=2;i*i<=x;i++){
if(x&&x%i==0){
ans=ans/i*(i-1);
while(x%i==0)
x/=i;
}
}
if(x>1) ans=ans/x*(x-1);
return ans;
}
int main()
{
scanf("%lld", &n);
int k=int(sqrt(n+0.5));
for(int i=1;i<=k;i++)
{
if(n%i==0)
{
ans += i*(phi(n/i));
if(i*i != n) ans+=n/i * (phi(i));
}
}
printf("%lldn", ans);
}
|
2018 蓝桥国赛第六题
- 显然也是枚举约数，但需要$O(n)$线性筛求出$[1,10^7]$的$phi$
- 时间复杂度$O(n)$
近期评论