BZOJ 2705([SDOI2012]Longge的问题-欧拉函数φ(i))

2705: [SDOI2012]Longge的问题

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 375  Solved: 239
[Submit][Status][Discuss]

Description

Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数,为N。

Output

一个整数,为所求的答案。

Sample Input

6

Sample Output

15

HINT

【数据范围】

对于60%的数据,0<N<=2^16。

对于100%的数据,0<N<=2^32。

 

欧拉函数

枚举n的约数k,令s(k)为满足gcd(m,n)=k,(1<=m<=n)  m的个数,则ans=sigma(k*s(k)) (k为n的约数)

 因为gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)

 枚举n的约数即可,复杂度o(sqrt(n))

PS:刚刚ksy告诉我C++,直接读int比读char转int慢(——0)


#include<cstdio>

include<cstring>

include<cstdlib>

include<cmath>

include<functional>

include<algorithm>

include<cctype>

include<iostream>

using namespace std;

define MAXN (2<<31)

long long ans=0,n; long long phi(long long n) { if (n==1) return 1; // cout<<n; long long ans=1; for (long long i=2;ii<=n;i++) if (n%i==0) { int k=0; while (n%i==0) {k++,n/=i;} ans=i-1; for (int j=2;j<=k;j++) ans=i;
} if (n>1) ans
=n-1; // cout<<' '<<ans<<endl; return ans; } int main() { cin>>n; for (int i=1;ii<=n;i++) if (n%i==0) { ans+=(long long)iphi(n/i); if (ii<n) ans+=(long long)n/iphi(i);
} cout<<ans<<endl; return 0; }