BZOJ 2705([SDOI2012]Longge的问题-欧拉函数φ(i))
2705: [SDOI2012]Longge的问题
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 375 Solved: 239
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
Sample Output
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; }
发表评论